/*
 Navicat Premium Dump SQL

 Source Server         : siu
 Source Server Type    : MySQL
 Source Server Version : 80021 (8.0.21)
 Source Host           : 120.46.13.13:3306
 Source Schema         : blog

 Target Server Type    : MySQL
 Target Server Version : 80021 (8.0.21)
 File Encoding         : 65001

 Date: 17/07/2024 15:09:00
*/

SET NAMES utf8mb4;
SET FOREIGN_KEY_CHECKS = 0;

-- ----------------------------
-- Table structure for articles
-- ----------------------------
DROP TABLE IF EXISTS `articles`;
CREATE TABLE `articles` (
  `id` bigint unsigned NOT NULL AUTO_INCREMENT,
  `user_id` bigint unsigned NOT NULL,
  `category_id` bigint unsigned NOT NULL,
  `title` varchar(50) NOT NULL,
  `content` longtext NOT NULL,
  `head_image` longtext,
  `read_cnt` bigint unsigned NOT NULL,
  `status` bigint unsigned NOT NULL,
  `created_at` datetime(3) NOT NULL,
  `updated_at` datetime(3) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=21 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;

-- ----------------------------
-- Records of articles
-- ----------------------------
BEGIN;
INSERT INTO `articles` (`id`, `user_id`, `category_id`, `title`, `content`, `head_image`, `read_cnt`, `status`, `created_at`, `updated_at`) VALUES (2, 1, 3, '计算机网络和因特网', '<h2 style=\"text-align: justify; line-height: 1.5;\">计算机网络</h2><p style=\"text-align: justify;\">​ 起源是为了形成一个自主、自治、互联的计算机通信系统。</p><h3 style=\"text-align: justify; line-height: 1.5;\">构成描述</h3><p style=\"text-align: justify;\">​ 因特网也被称为“网中网”，我们所用的网络都是大网中的小网（套娃）。</p><ul><li style=\"text-align: justify;\">接入网络的设备——网络边缘</li><li style=\"text-align: justify;\"><strong>通信链路</strong>（communication link）——接入网</li><li style=\"text-align: justify;\"><strong>分组交换机</strong>（packet switch）——网络核心</li><li style=\"text-align: justify;\"><strong>协议</strong>：控制发送、接收信息。比如，TCP, IP, HTTP等等。每个层次有每个层次的协议。</li><li style=\"text-align: justify;\"><strong>网络标准</strong></li></ul><p style=\"text-align: justify;\"><img src=\"https://i.loli.net/2020/03/19/J1qlUrQx9LiTFY2.png\" alt=\"\" data-href=\"\" style=\"\"></p><h3 style=\"text-align: justify; line-height: 1.5;\">服务描述</h3><ul><li style=\"text-align: justify;\">为应用程序提供服务的基础设施即用户使用应用。</li><li style=\"text-align: justify;\">应用程序编程接口即编写应用。</li></ul><h2 style=\"text-align: justify; line-height: 1.5;\">网络边缘（Network Edge）</h2><p style=\"text-align: justify;\">​ 与因特网相接的计算机及其他设备位于因特网的边缘，称为<strong>端系统</strong>。</p><p style=\"text-align: justify;\">端系统 = 主机，可以被划为下面两种：</p><ul><li style=\"text-align: justify;\">客户（client）</li><li style=\"text-align: justify;\">服务器（server）：比如有企业存储大量数据的大型<strong>数据中心</strong>（data centers）</li></ul><h3 style=\"text-align: justify; line-height: 1.5;\">接入网（Access Networks）</h3><p style=\"text-align: justify;\">​ 网络边缘的端系统 通过 <strong>接入网</strong>（物理链路） 连接到 <strong>边缘路由器</strong>（端系统到任何其他远程端系统的路径上的第一台路由器）。</p><h4 style=\"text-align: justify; line-height: 1.5;\">家庭接入：DSL、电缆、FTTH、拨号和卫星</h4><ul><li style=\"text-align: justify;\"><strong>数字用户线</strong>（digital subscriber line，<strong>DSL</strong>）</li></ul><p style=\"text-align: justify;\">​ 利用<strong>电话线路</strong>接入网络。其中 <strong>ADSL</strong>是非对称的数字用户线，基本都用ADSL，因为一般下行的数据量都远大于上行的数据量，所以要设计成非平衡的链路。</p><p style=\"text-align: justify;\">​ 采用<strong>独占</strong>的<strong>频分多路复用</strong>来传输。因为利用的是原有的电话线路，所以需要将DSL传输的网络信号（上行、下行）和电话信号通过频分多路复用来区分开来。</p><p style=\"text-align: justify;\"><br></p><table style=\"width: auto;\"><tbody><tr><th colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">频段</th><th colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">传输信号</th></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">0~4K</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">电话语音线路</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">4K~50K</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">上行信号</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">50K~1M</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">下行信号</td></tr></tbody></table><p style=\"text-align: justify;\"><img src=\"https://i.loli.net/2020/03/20/oCDhqtVGuRLjenm.png\" alt=\"截屏2020-03-20上午12.22.20.png\" data-href=\"\" style=\"width: 50%;\"></p><ul><li style=\"text-align: justify;\">电缆因特网接入（cable Internet access）利用有线电视网接入网络。结构上，通过粗的同轴电缆接入社区，再用细的同轴电缆接入每家每户。采用共享的频分多路复用来传输。</li></ul><p style=\"text-align: justify;\"><img src=\"https://i.loli.net/2020/03/20/w1BdRQcMi5KS7Iz.png\" alt=\"\" data-href=\"\" style=\"width: 50%;\"></p><ul><li style=\"text-align: justify;\"><strong>混合光纤同轴电缆</strong>（<strong>HFC</strong>）</li></ul><p style=\"text-align: justify;\">​ <strong>同轴电缆</strong>和<strong>光纤节点</strong>相连再接入边缘路由器。</p><p style=\"text-align: justify;\">​ <strong>不对称</strong>的<strong>竞争式协议</strong>，最高可达到30Mbps的下行速率和2Mbps的上行速率。由于采用竞争式协议，在用户少时使用体验优于普通的电缆因特网接入，但是在用户多时容易造成卡顿。</p><p style=\"text-align: justify;\"><img src=\"https://i.loli.net/2020/03/20/xsZF9RbLfSq82or.png\" alt=\"\" data-href=\"\" style=\"width: 50%;\"></p><h4 style=\"text-align: justify; line-height: 1.5;\">企业（家庭）接入：以太网和WiFi</h4><ul><li style=\"text-align: justify;\"><strong>以太网</strong>：使用双绞铜线与一台以太网交换机相连，速率可达到100Mbps、1Gbps、10Gbps。</li><li style=\"text-align: justify;\"><strong>WiFi</strong>：IEEE802.11技术无线LAN，范围在几十米内。</li></ul><h4 style=\"text-align: justify; line-height: 1.5;\">广义无线接入：4G和5G</h4><p style=\"text-align: justify;\">​ 详见第六章</p><h3 style=\"text-align: justify; line-height: 1.5;\">物理媒体（Physical Media）</h3><ul><li style=\"text-align: justify;\">导引型媒体（guided media）：信号在固体媒体中传输，比如光缆、双绞铜线和同轴电缆。</li><li style=\"text-align: justify;\">非导引型媒体（unguided media）：电波在空气中传播，比如无线局域网或数字卫星频道。</li></ul><h2 style=\"text-align: justify; line-height: 1.5;\">网络核心（Network Core）</h2><p style=\"text-align: justify;\">​ 网络核心：由端系统的分组交换机和链路构成的网状网络。下图标亮部分即使网络核心。</p><p style=\"text-align: justify;\">​ 一共有三种交换方式：报文交换（很少使用）、分组交换和电路交换</p><p style=\"text-align: justify;\"><img src=\"https://i.loli.net/2020/03/20/dAzBna3i9lZU2uN.png\" alt=\"\" data-href=\"\" style=\"width: 50%;\"></p><h3 style=\"text-align: justify; line-height: 1.5;\">分组交换（Packet Switching）</h3><p style=\"text-align: justify;\">​ 端系统之间彼此传输报文，分组交换中，将长报文划分为分组，分组再通过通信链路和分组交换机（分为路由器和链路层交换机）传送。</p><ol><li style=\"text-align: justify;\">存储转发传输（Store-and-Forward Transmission）​ 分组交换和报文交换都采用了存储转发的传输形式。但分组交换的存储转发以分组为单位，即交换机接收到整个分组后才能输出该分组的数据；而报文交换的存储转发单位为报文，需要交换机接收到整个报文后才能输出。​ 传输相同大小的数据包，分组交换比报文交换更快。下面是分组交换传输3L大小的报文的时间流，报文分为3个大小为L的分组，根据分组交换原理，一共耗费了 4L/R 时间完成传输（即存储转发时延）。而如果使用报文传输同样的3L大小的报文则需要耗费 6L/R 时间。</li><li style=\"text-align: justify;\">排队时延（Queuing Delay）和分组丢失（Packet Loss）​ 分组交换机有有一个输出缓存（output buffer），分组可能会在分组交换机上排队等待输出，造成排队时延。​ 分组交换机的缓存空间是有限的，所以在过于拥堵时会产生分组丢失（丢包）。</li><li style=\"text-align: justify;\">转发表（Forwarding Table）和路由选择协议（Routing Protocol）路由：分组中包括IP地址；转发：路由器中将目的地址映射为输出链路。</li></ol><h3 style=\"text-align: justify; line-height: 1.5;\">电路交换（Circuit Switching）</h3><p style=\"text-align: justify;\">​ <strong>端到端连接</strong>（end- to-end connection）：在发送数据之前，必须先在发送和接收两端建立端到端连接，并预留一部分带宽。而分组交换不预留，所以会造成排队和丢包。</p><p style=\"text-align: justify;\"><img src=\"https://i.loli.net/2020/03/20/D91fBHdvxo24MFT.png\" alt=\"\" data-href=\"\" style=\"\"></p><h4 style=\"text-align: justify; line-height: 1.5;\">频分多路复用（FDM）</h4><p style=\"text-align: justify;\">​ 链路中的每条连接专用一个频段。</p><p style=\"text-align: justify;\"><img src=\"https://i.loli.net/2020/03/20/NubPYJA6WrcvsqI.png\" alt=\"\" data-href=\"\" style=\"width: 50%;\"></p><h4 style=\"text-align: justify; line-height: 1.5;\">时分多路复用（TDM）</h4><p style=\"text-align: justify;\">​ 远距离传输会有衰减，所以考虑用<strong>数字信号</strong>进行传输。在时域上对信号进行<strong>采样</strong>，接收时再将采样信号恢复。</p><p style=\"text-align: justify;\">​ TDM在时域上被划分为固定的<strong>帧</strong>（frame），每帧又被划分为固定数量的<strong>时隙</strong>（slot），链路中的每条连接专用一个时隙。</p><p style=\"text-align: justify;\"><img src=\"https://i.loli.net/2020/03/21/yLN9bmafTdIqj6c.png\" alt=\"\" data-href=\"\" style=\"\"></p><h3 style=\"text-align: justify; line-height: 1.5;\">分组交换 &amp; 电路交换</h3><p style=\"text-align: justify;\">​ 分组交换的性能优于电路交换，适用于随机数据，可以满足更多用户。</p><p style=\"text-align: justify;\">​ 电路交换需要预留带宽，相当于固定了链路用户的数量。而分组交换不需要预留带宽，用户使用网络是有一定概率的，在一个时刻较多人使用的概率其实相对较低，所以一条链路可以给更多的用户使用。</p><p style=\"text-align: justify;\">​ 电路交换适用于特殊情况，比如要保障传输数据能力。</p><h3 style=\"text-align: justify; line-height: 1.5;\">网络结构</h3><p style=\"text-align: justify;\">​ 网络结构是网中之网，具有层次结构。</p><ul><li style=\"text-align: justify;\"><strong>ISP</strong>：ISP分为许多层级，比如<strong>第一层ISP</strong>（tier-1 ISP）、<strong>区域ISP</strong>（regional ISP）、<strong>接入ISP</strong>（access ISP）。端系统通过接入ISP与因特网相连，全球的ISP通过各个层级相连，形成了互联网的互联。</li><li style=\"text-align: justify;\">因特网交换点（Internet Exchange Point，<strong>IXP</strong>）：由第三方公司创建，IXP是一个汇合点，多个ISP在此处对等。</li></ul><p style=\"text-align: justify;\"><img src=\"https://i.loli.net/2020/03/21/NugS6r92GDaCqeJ.png\" alt=\"\" data-href=\"\" style=\"width: 50%;\"></p><h2 style=\"text-align: justify; line-height: 1.5;\">协议（Protocol）</h2><p style=\"text-align: justify;\">​ 协议定义了在两个或多个通信实体之间交换的报文格式和次序，以及报文发送和/或接收一条报文或其他时间所采取的动作。</p><p style=\"text-align: justify;\">​ 协议三大要素：</p><ul><li style=\"text-align: justify;\">语法（Syntax）：每一段内容符合一定规则的格式，比如一个报文前8位是原地址，后八个是目的地址（只是举例，不要当真）之类。</li><li style=\"text-align: justify;\">语义（Semantics）：每一段内容需要代表某种意义，比如原地址部分的二进制到底是指哪个地址。</li><li style=\"text-align: justify;\">同步（Timing）：通信的过程，即每一段任务的执行顺序。</li></ul><p style=\"text-align: justify;\"><img src=\"https://i.loli.net/2020/03/22/RS7Lpk2YjGtCnKV.png\" alt=\"\" data-href=\"\" style=\"width: 50%;\"></p><h2 style=\"text-align: justify; line-height: 1.5;\">协议层次（Protocol Layer）及其服务模型</h2><h3 style=\"text-align: justify; line-height: 1.5;\">五层因特网协议栈</h3><p style=\"text-align: justify;\">​ 因特网协议栈由5个层次组成：物理层、链路层、网络层、传输层和应用层。因特网协议栈是一个理想模型。</p><p style=\"text-align: justify;\">​ 下层为上层提供服务。越下面的层，越靠近硬件；越上面的层，越靠近用户。</p><p style=\"text-align: justify;\"><img src=\"https://i.loli.net/2020/03/22/oYnb8OzPqg461Ux.png\" alt=\"截屏2020-03-22上午12.23.35.png\" data-href=\"\" style=\"\"></p><p style=\"text-align: justify;\"><br></p><table style=\"width: auto;\"><tbody><tr><th colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: center;\">层次</th><th colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">功能</th></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: center;\">应用层（Application Layer）</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">支持网络应用，应用协议仅仅是网络应用的一个组成部分，运行在不同主机上的进程则使用应用层协议进行通信。</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: center;\">传输层（Transport Layer）</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">负责为信源和信宿提供应用程序进程间的数据传输服务，这一层上主要定义了两个传输协议，传输控制协议即TCP和用户数据报协议UDP。</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: center;\">网络层（Network Layer）</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">负责将<strong>数据报</strong>独立地从信源发送到信宿，主要解决路由选择、拥塞控制和网络互联等问题。</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: center;\">链路层（Link Layer）</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">负责将IP数据报封装成合适在物理网络上传输的<strong>帧</strong>格式并传输，或将从物理网络接收到的帧解封，取出IP数据报交给网络层。</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: center;\">物理层（Physical Layer）</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">负责将<strong>比特流</strong>在结点间传输，即负责物理传输。该层的协议既与链路有关也与传输介质有关。</td></tr></tbody></table><h3 style=\"text-align: justify; line-height: 1.5;\">OSI模型</h3><p style=\"text-align: justify;\">​ OSI模型由国际标准化组织（ISO）制定，实际并没有应用，只有理论。</p><p style=\"text-align: justify;\">​ OSI模型由7层组成：应用层、表示层、会话层、传输层、网络层、数据链路层、物理层。</p><h3 style=\"text-align: justify; line-height: 1.5;\">封装（Encapsulation）</h3><p style=\"text-align: justify;\">​ 在发送端，</p><ol><li style=\"text-align: justify;\">应用层：将 应用层报文（application-layer message）M传送给传输层；</li><li style=\"text-align: justify;\">传输层：接收报文M，附上传输层首部信息Ht（包括差错检测位信息等），构成 传输层报文段（transport-layer segment），将其传递给网络层；</li><li style=\"text-align: justify;\">网络层：接收传输层报文段，附上网络层首部信息Hn（包括源和目的地址等），构成 网络层数据段（network-layer datagram），将其传递给网络层；</li><li style=\"text-align: justify;\">链路层：接收网络层数据段，附上链路层首部信息Hl，构成 链路层帧（link-layer frame），将其传递给物理层；</li><li style=\"text-align: justify;\">物理层：负责比特流物理传输。在接收端以反方向重构报文段。</li></ol><p style=\"text-align: justify;\"><img src=\"https://i.loli.net/2020/03/22/uBFK4rGifLvsHqE.png\" alt=\"\" data-href=\"\" style=\"width: 50%;\"></p><h2 style=\"text-align: justify; line-height: 1.5;\">物理层概述</h2><p style=\"text-align: justify;\">​ 在两个物理媒体间进行比特流传输，上层都是逻辑链接，只有物理层是实际的物理连接。</p><h3 style=\"text-align: justify; line-height: 1.5;\">物理层基本目标</h3><ul><li style=\"text-align: justify;\">保证发送信号“0”和“1”的正确性以及发送和接收的一致性；</li><li style=\"text-align: justify;\">比特流传输的模式、速度、持续时间和信号失真；</li><li style=\"text-align: justify;\">接口设计：引脚数目、功能等等；</li><li style=\"text-align: justify;\">信号传输的程序：如何安排传输过程和事件次序。</li></ul><h3 style=\"text-align: justify; line-height: 1.5;\">物理层的基本特性</h3><ul><li style=\"text-align: justify;\">机械特性：指明接口所用接线器的形状和尺寸、引线数目和排列、固定和锁定装置等；</li><li style=\"text-align: justify;\">电气特性：指明传输模式、电压范围、编码、阻抗匹配、传输速率以及传输距离等等；</li><li style=\"text-align: justify;\">功能特性：指明各条物理线路的功能，比如某条线上出现的某一电平的电压表示何种意义，物理接口信号线按功能分为四类：数据线、控制线、定时线和地线；</li><li style=\"text-align: justify;\">规程特性：指明各物理线路工作规程和时序的关系，比如对于不同功能的各种可能事件的出现顺序，信号传输的模式：单工（仅单向通行）、半双工（双方通，但一个时刻仅一方通）、全双工（双方随时通）。</li></ul><h2 style=\"text-align: justify; line-height: 1.5;\">基本通信原理</h2><h3 style=\"text-align: justify; line-height: 1.5;\">基本概念</h3><ul><li style=\"text-align: justify;\">数据（data）：对于客观事实描述的物理符号，包括数字、文本、语言、图像等等；</li><li style=\"text-align: justify;\">信息（information）：数据的集合；</li><li style=\"text-align: justify;\">信号（signal）：数据传输中的表现形式，比如模拟信号、数字信号；</li><li style=\"text-align: justify;\">信道（channel）：往固定方向传输信息的媒介。</li></ul><p style=\"text-align: justify;\"><strong>模拟传输VS数字传输</strong></p><p style=\"text-align: justify;\"><br></p><table style=\"width: auto;\"><tbody><tr><th colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">传输方式</th><th colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">优点</th><th colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">缺点</th></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">模拟</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">对信道有高利用率</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">不抗噪</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">数字</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">信号不易失真</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">需要更宽的带宽</td></tr></tbody></table><h3 style=\"text-align: justify; line-height: 1.5;\">信道特性</h3><ul><li style=\"text-align: justify;\"></li><li style=\"text-align: justify;\">波特率（Baud rate）：传输码元的速率。</li><li style=\"text-align: justify;\"></li><li style=\"text-align: justify;\">信道容量（Channel capacity）：在一个信道中能够可靠地传送信息时可达速率的最小上界，单位 bps。</li><li style=\"text-align: justify;\"></li><li style=\"text-align: justify;\">传输延迟（Transmission delay）：包括发送到接受的处理事件、电信号的响应时间、中间介质的传输时间。</li><li style=\"text-align: justify;\">奈奎斯特定理（Nyquist’s Law）对于理想的低通信号，在一个频带宽度为 W 的信道，其码元的最大传输速率 = 2W Baud对于理想的带通信号，在一个频带宽度为 W 的信道，其码元的最大传输速率 = W Baud</li><li style=\"text-align: justify;\"></li></ul><h3 style=\"text-align: justify; line-height: 1.5;\">模拟/数字信号传输</h3><p style=\"text-align: justify;\">​ 模拟信道只能传输模拟信号，数字信道只能传输数字信号。</p><h4 style=\"text-align: justify; line-height: 1.5;\">调制解调器</h4><p style=\"text-align: justify;\">​ 数字/模拟信号 经过 <strong>调制</strong> 变成 <strong>模拟信号</strong>，如此可在 模拟信道 上传输，再经过 <strong>解调</strong> 变成 数字/模拟信号。</p><p style=\"text-align: justify;\"><img src=\"https://i.loli.net/2020/03/23/4mKvzSkIDigxhFX.png\" alt=\"\" data-href=\"\" style=\"width: 649.00px;height: 226.06px;\"></p><h4 style=\"text-align: justify; line-height: 1.5;\">编码解码器</h4><p style=\"text-align: justify;\">​ 数字/模拟信号 经过 <strong>编码</strong> 变成 <strong>数字信号</strong>，如此可在 数字信道 上传输，再经过 <strong>解码</strong> 变成 数字/模拟信号。</p><p style=\"text-align: justify;\"><img src=\"https://i.loli.net/2020/03/23/OcMLw2JjiA9FsSP.png\" alt=\"截屏2020-03-23上午1.37.30.png\" data-href=\"\" style=\"width: 634.00px;height: 225.88px;\"></p><h4 style=\"text-align: justify; line-height: 1.5;\">调制（Modulation）：数字信号到模拟信号</h4><p style=\"text-align: justify;\">​ 从数字信号到模拟信号的调制主要有三种方法：</p><ul><li style=\"text-align: justify;\">调幅（Amplitude Modulation，AM）把数字信号转化成不同幅度的正弦信号。</li><li style=\"text-align: justify;\">调频（Frequency Modulation，FM）把数字信号转化成不同频率的正弦信号。</li><li style=\"text-align: justify;\">调相（Phase Modulation，PM）把数字信号转化成不同相位的正弦信号。</li></ul><h4 style=\"text-align: justify; line-height: 1.5;\">脉码调制（Pulse Code Modulation, PCM）</h4><p style=\"text-align: justify;\">​ 模拟信号变成数字信号。</p><p style=\"text-align: justify;\">脉码调制步骤：</p><ol><li style=\"text-align: justify;\">采样（Sampling system）采样频率是信号频率的两倍，则可不失真地恢复原始信号。</li><li style=\"text-align: justify;\">量化（Quantify）取整采样信号。</li><li style=\"text-align: justify;\">编码（Coding）量化后的信号编码成二进制。</li></ol><p style=\"text-align: justify;\"><img src=\"https://i.loli.net/2020/03/23/ze59JcGyOojH2Dx.png\" alt=\"\" data-href=\"\" style=\"width: 663.00px;height: 524.29px;\"></p><h4 style=\"text-align: justify; line-height: 1.5;\">数字信号编码（Digital signal coding）</h4><p style=\"text-align: justify;\">​ 数字信号到数字信号。</p><h5 style=\"text-align: justify; line-height: 1.5;\">不归零编码（Non-Return-To-Zero, NRZ）</h5><p style=\"text-align: justify;\">​ 主要介绍两种不归零编码。</p><ul><li style=\"text-align: justify;\">Non-Return-To-Zero Level (NRZ-L) Coding​ 高电平表示“1”，低电平表示“0”。NRZ-L的优点：简单好实现NRZ-L的缺点：难以分清二进制一位的开始和结束，所以必须要带同步时钟（外同步）来同步。可以把上图的虚线当作是同步时钟，当把虚线去掉是，相同电平的信号就不好判断开始和结束了。在传输全“1”或全“0”信号时，此时传输的只有直流分量（傅立叶分不出正弦或余弦分量），这样线路上会有比较大的噪声。</li><li style=\"text-align: justify;\">反向不归零编码（NRZ-I）​ 遇“1”反向。只能解决NRZ-L的部分问题（全“1”问题，不再是直流）</li></ul><p style=\"text-align: justify;\"><strong>外同步</strong>（External synchronization）</p><p style=\"text-align: justify;\">​ 给系统一个同步时钟信号，设置一个周期的宽度。</p><p style=\"text-align: justify;\">​ 外同步有诸多不便，于是有了自同步的曼切斯特编码。</p><h5 style=\"text-align: justify; line-height: 1.5;\">曼切斯特编码（Manchester encoding）</h5><p style=\"text-align: justify;\">​ 每个编码由两段组成，“1”：先高后低；“0”：先低后高（可以反过来定义）。</p><p style=\"text-align: justify;\"><img src=\"https://i.loli.net/2020/03/23/CwpZhdnVO65m2DX.png\" alt=\"\" data-href=\"\" style=\"width: 680.00px;height: 275.02px;\"></p><p style=\"text-align: justify;\">曼切斯特编码的优点（解决了不归零编码的问题）：</p><ul><li style=\"text-align: justify;\">自同步，不需要同步时钟；</li><li style=\"text-align: justify;\">直流分量为0。</li></ul><p style=\"text-align: justify;\">曼切斯特编码的缺点：</p><ul><li style=\"text-align: justify;\">基频增加：基频是不归零编码的两倍，从而比特率变成了不归零编码的一半；</li><li style=\"text-align: justify;\">二义性：组合情况有两种。</li></ul><h5 style=\"text-align: justify; line-height: 1.5;\">差分曼切斯特编码（Differential Manchester encoding）</h5><p style=\"text-align: justify;\">​ 解决曼切斯特编码的二义性。</p><ul><li style=\"text-align: justify;\">“1”：自己的前半波与前一个编码的后半波相同；</li><li style=\"text-align: justify;\">“0”：自己的前半波与前一个编码的后半波相反。有两种画法，初始为高、初始为低，两种画法结果对称。</li></ul><p style=\"text-align: justify;\"><img src=\"https://i.loli.net/2020/03/23/mdYhZEKHulpkjTW.png\" alt=\"\" data-href=\"\" style=\"width: 674.00px;height: 214.41px;\"></p><p style=\"text-align: justify;\">​ 差分曼切斯特编码的优点：</p><ul><li style=\"text-align: justify;\">解决NRZ问题</li><li style=\"text-align: justify;\">解决二义性问题</li></ul><p style=\"text-align: justify;\">​ 差分曼切斯特编码的缺点（同曼切斯特编码）：</p><ul><li style=\"text-align: justify;\">基频翻倍</li><li style=\"text-align: justify;\">高频噪声增加</li></ul><h5 style=\"text-align: justify; line-height: 1.5;\">块编码（Block encoding）</h5><ol><li style=\"text-align: justify;\">将原信号每 m bits 分为一块；</li><li style=\"text-align: justify;\">把 m bits 的每块映射成 n bits 的块（m &lt; n）；</li><li style=\"text-align: justify;\">将 n bits 的块重新组合起来。</li></ol><p style=\"text-align: justify;\"><img src=\"https://i.loli.net/2020/03/23/5D78VTnaSXjMyfR.png\" alt=\"\" data-href=\"\" style=\"width: 649.00px;height: 1270.82px;\"></p><h3 style=\"text-align: justify; line-height: 1.5;\">多路复用（Multiplexing）</h3><h4 style=\"text-align: justify; line-height: 1.5;\">频分多路复用（Frequency division multiplexing，FDM）</h4><p style=\"text-align: justify;\">​ 见 <a href=\"https://gy23333.github.io/2020/03/16/%E3%80%8A%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BD%91%E7%BB%9C-%E8%87%AA%E9%A1%B6%E5%90%91%E4%B8%8B%E6%96%B9%E6%B3%95%E3%80%8B%E7%AC%94%E8%AE%B0/#%E9%A2%91%E5%88%86%E5%A4%9A%E8%B7%AF%E5%A4%8D%E7%94%A8%EF%BC%88FDM%EF%BC%89\" target=\"\">频分多路复用</a> 。</p><h4 style=\"text-align: justify; line-height: 1.5;\">时分多路复用（Time division multiplexing，TDM）</h4><p style=\"text-align: justify;\">​ 见 <a href=\"https://gy23333.github.io/2020/03/16/%E3%80%8A%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BD%91%E7%BB%9C-%E8%87%AA%E9%A1%B6%E5%90%91%E4%B8%8B%E6%96%B9%E6%B3%95%E3%80%8B%E7%AC%94%E8%AE%B0/#%E6%97%B6%E5%88%86%E5%A4%9A%E8%B7%AF%E5%A4%8D%E7%94%A8%EF%BC%88TDM%EF%BC%89\" target=\"\">时分多路复用</a> 。</p><h4 style=\"text-align: justify; line-height: 1.5;\">波分多路复用（Wavelength division multiplexing，WDM）</h4><p style=\"text-align: justify;\">​ 和FDM原理相同，但主要在光波中采用。</p><h4 style=\"text-align: justify; line-height: 1.5;\">码分多路复用（Code division multiplexing，CDM）</h4><p style=\"text-align: justify;\">举例说明</p><p style=\"text-align: justify;\">​ 每台设备都给一个不同向量的码片，比如手机A的码片为A，手机B的码片为B。不同设备的码片正交，即</p><p style=\"text-align: justify;\">{A×B=0A×A=1{𝐴×𝐵=0𝐴×𝐴=1</p><p style=\"text-align: justify;\">​ 要向手机A发送数据a，向手机B发送数据b，则在信道中发送 a×A+b×B𝑎×𝐴+𝑏×𝐵。</p><p style=\"text-align: justify;\">​ 在手机A接收数据时，将接收到的信号乘A。</p><p style=\"text-align: justify;\">(a×A+b×B)×A=a×A×A+b×B×A=a(𝑎×𝐴+𝑏×𝐵)×𝐴=𝑎×𝐴×𝐴+𝑏×𝐵×𝐴=𝑎</p><p style=\"text-align: justify;\">​ 同理手机B，如此两台设备同时利用一条信道传输，并成功分离各自的数据。</p><h2 style=\"text-align: justify; line-height: 1.5;\">延时、丢包、吞吐量</h2><h3 style=\"text-align: justify; line-height: 1.5;\">延时（delay）</h3><p style=\"text-align: justify;\">​ 现实中的计算机系统不是理想系统，事件是随机突发的，所以不可避免的存在延时<img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/delay.png\" alt=\"delay.png\" data-href=\"\" style=\"width: 730.00px;height: 287.59px;\"></p><p style=\"text-align: justify;\">​ 数据包的延时由四个部分组成：</p><p style=\"text-align: justify;\">dnodal=dprop+dqueue+dtrans+dprop𝑑𝑛𝑜𝑑𝑎𝑙=𝑑𝑝𝑟𝑜𝑝+𝑑𝑞𝑢𝑒𝑢𝑒+𝑑𝑡𝑟𝑎𝑛𝑠+𝑑𝑝𝑟𝑜𝑝</p><ul><li style=\"text-align: justify;\">处理时延（Nodal Processing Delay，dproc𝑑𝑝𝑟𝑜𝑐）​ 路由器接收到分组对其进行处理的时间（比如差错检测），耗时很短，毫秒级。</li><li style=\"text-align: justify;\">排队时延（Queuing Delay，dqueue𝑑𝑞𝑢𝑒𝑢𝑒）​ 分组在链路上等待传输的时间，取决于先期到达的正在排队等待向链路传输的分组数量。</li></ul><h3 style=\"text-align: justify; line-height: 1.5;\">丢包（Packet Loss）</h3><p style=\"text-align: justify;\">​ 流量强度（traffic intensity）代表了路由器上排队的拥堵率。</p><p style=\"text-align: justify;\">traffic intensity=(L×a)/R𝑡𝑟𝑎𝑓𝑓𝑖𝑐 𝑖𝑛𝑡𝑒𝑛𝑠𝑖𝑡𝑦=(𝐿×𝑎)/𝑅</p><p style=\"text-align: justify;\">​ 其中，L —— 分组长度（bits）；</p><p style=\"text-align: justify;\">​ R —— 链路带宽（bps）；</p><p style=\"text-align: justify;\">​ a —— 平均分组到达速率</p><ul><li style=\"text-align: justify;\">流量强度接近0时，几乎没有分组到达，排队延时很小；</li><li style=\"text-align: justify;\">流量强度0～1时，平均排队长度越来越长，排队延时越来越长；</li><li style=\"text-align: justify;\">流量强度接近1时，存在到达率超过传输时间间隔，拥堵。<img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/traffic%20intensity.png\" alt=\"traffic intensity.png\" data-href=\"\" style=\"width: 325.00px;height: 283.10px;\"></li></ul><p style=\"text-align: justify;\">​ 路由器的排队容量是有限的，当分组到达一个已满的队列时，路由器将丢弃该分组，产生丢包。</p><h3 style=\"text-align: justify; line-height: 1.5;\">吞吐量（Throughput）</h3><p style=\"text-align: justify;\">​ 从主机A到主机B传文件，B接收文件的速率为<strong>瞬时吞吐量</strong>（instantaneous throughput），单位bps；所有时间的平均速率为<strong>平均吞吐量</strong>（average throughput）。</p><p style=\"text-align: justify;\">​ 串联链路吞吐量取决于<strong>瓶颈链路</strong>（bottleneck link）。</p><p style=\"text-align: justify;\">Throughput=min{R1,R2,...,RN}𝑇ℎ𝑟𝑜𝑢𝑔ℎ𝑝𝑢𝑡=𝑚𝑖𝑛{𝑅1,𝑅2,...,𝑅𝑁<img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Throughput.png\" alt=\"Throughput.png\" data-href=\"\" style=\"width: 404.00px;height: 85.85px;\"></p><p><br></p>', '', 15, 0, '2024-07-16 23:28:15.496', '2024-07-17 09:43:13.893');
INSERT INTO `articles` (`id`, `user_id`, `category_id`, `title`, `content`, `head_image`, `read_cnt`, `status`, `created_at`, `updated_at`) VALUES (6, 4, 3, '应用层（Application Layer）——DNS', '<h2 style=\"text-align: justify; line-height: 1.5;\">DNS</h2><p style=\"text-align: justify;\">​   域名系统（Domain Name System，DNS）通过分布式的数据库来实现IP地址和域名的映射。</p><ul><li style=\"text-align: justify;\"><strong>层级结构的域名服务器提供分布式的数据库</strong></li><li style=\"text-align: justify;\"><strong>应用层协议</strong>：主机和域名服务器通过通信来实现IP地址和域名的转换</li><li style=\"text-align: justify;\"></li></ul><p>DNS作为一个<strong>网络核心功能</strong>，为什么要放在应用层？<br>  与网络结构设计理念有关，网络中主机很多映射很复杂，希望将复杂度留在端系统中，而不是在网络核心。</p><h3 style=\"text-align: justify; line-height: 1.5;\">DNS服务</h3><ul><li style=\"text-align: justify;\">IP地址和域名的转换</li><li style=\"text-align: justify;\">主机的别名</li><li style=\"text-align: justify;\">邮件服务的别名</li><li style=\"text-align: justify;\">负荷分配：有些Web可能有多个服务器，即会有多个IP地址对应一个域名，可调整IP地址的顺序以分配负荷。</li></ul><h3 style=\"text-align: justify; line-height: 1.5;\">DNS：分布式、层级的数据库</h3><p><br></p><p>为什么要选用分布的DNS，而不采用集中式的DNS？</p><ul><li>单点可能失效：一个故障就gg了</li><li>流量问题：所有客户机都访问一个域名服务器，会产生很大的流量</li><li>远程的集中式数据库：客户机要访问可能要花费很多时间，RTT会很大，造成大时延</li></ul><p style=\"text-align: justify;\">  DNS采用三层结构</p><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Network_DNS%20Server.png\" alt=\"DNS Server.png\" data-href=\"\" style=\"width: 50%;\"></p><p style=\"text-align: justify;\">一个客户机得到<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>www.amazon.com</code></span>的IP地址的步骤：</p><ol><li style=\"text-align: justify;\">客户机先查询根域名服务器，得到顶级域名服务器<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>.com DNS server</code></span>的地址；</li><li style=\"text-align: justify;\">客户机查询顶级域名服务器<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>.com DNS server</code></span>，得到权威域名服务器<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>amazon.com DNS server</code></span>的地址；</li><li style=\"text-align: justify;\">客户机查询权威域名服务器<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>amazon.com DNS server</code></span>，得到<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>www.amazon.com</code></span>的IP地址</li></ol><h4 style=\"text-align: justify; line-height: 1.5;\">根域名服务器（Root Name Server）</h4><ul><li style=\"text-align: justify;\">官方的服务器，是<u>连接的最后的方法</u>（如果知道下级域名服务器的地址就不需要再从头开始查询根域名服务器，不然会对根域名服务器产生很大的流量负荷）</li><li style=\"text-align: justify;\">对网络运行相当重要，离开根域名服务器网络无法正常工作</li><li style=\"text-align: justify;\">域名系统安全扩展（Domain Name System Security Extensions，DNSSEC） —— 对DNS提供给DNS客户端（解析器）的DNS数据来源进行认证，并验证不存在性和校验数据完整性验证。</li><li style=\"text-align: justify;\">ICANN（互联网名称与数字地址分配机构，Internet Corporation for Assigned Names and Numbers）—— 管理根域名服务器的组织</li><li style=\"text-align: justify;\"></li></ul><p>世界上现在有13个根域名服务器，分布在世界各地。</p><h4 style=\"text-align: justify; line-height: 1.5;\">顶层域名服务器（Top-Level Domain Server, TLD）</h4><ul><li style=\"text-align: justify;\">各种类型的TLD，比如<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>.com</code></span>、<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>.org</code></span>、<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>net</code></span>、<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>.edu</code></span>等等，国家的TLD，比如<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>.cn</code></span>、<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>.uk</code></span>等等。</li><li style=\"text-align: justify;\">Network Solutions：管理<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>.com</code></span>、<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>net</code></span>TLD的组织</li><li style=\"text-align: justify;\">Educause：管理<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>.edu</code></span>的组织</li></ul><h4 style=\"text-align: justify; line-height: 1.5;\">权威域名服务器（Authoritative Domain Server）</h4><ul><li style=\"text-align: justify;\">组织自己的DNS服务器，用来提供组织内部的域名到IP地址的映射</li><li style=\"text-align: justify;\">由组织自己或者服务提供商来维护</li></ul><h4 style=\"text-align: justify; line-height: 1.5;\">本地域名服务器（Local DNS Name Server）</h4><ul><li style=\"text-align: justify;\">严格来说不属于层级结构</li><li style=\"text-align: justify;\">每个ISP都会有一个本地域名服务器，也叫做<strong>默认域名服务器</strong>（default name server）</li><li style=\"text-align: justify;\">当主机要进行DNS查询时，查询会被直接送到本地的DNS服务器。</li><li style=\"text-align: justify;\">作用：</li></ul><h3 style=\"text-align: justify; line-height: 1.5;\">DNS查询方法</h3><h4 style=\"text-align: justify; line-height: 1.5;\">迭代查询（iterated query）</h4><p style=\"text-align: justify;\">  被联系到的服务器会将后一个服务器的名字反馈回来，即“我不认识这个域名，但是你可以去问那台服务器(=ﾟωﾟ)ﾉ”</p><p style=\"text-align: justify;\">  下面的迭代查询过程，利用本地域名服务器作为代理迭代查询域名对于的IP地址。</p><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Network_iterated-query.png\" alt=\"iterated query.png\" data-href=\"\" style=\"width: 50%;\"></p><h4 style=\"text-align: justify; line-height: 1.5;\">递归查询（recursive query）</h4><p style=\"text-align: justify;\">  把域名解析的负担交给了联系到的域名服务器，这种方法对于高级的负担增加，所以一般采用迭代查询而不采用递归查询。</p><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Network_recursive-query.png\" alt=\"recursive query.png\" data-href=\"\" style=\"width: 50%;\"></p><h3 style=\"text-align: justify; line-height: 1.5;\">DNS缓存和更新</h3><ul><li style=\"text-align: justify;\">一旦域名服务器学习到了一个映射，它就会<strong>缓存</strong>这个映射。缓存往往在本地域名服务器里，这样可以减轻根域名服务器的压力。</li><li style=\"text-align: justify;\"><strong>缓存有效时间TTL</strong>，过了有效时间该缓存就会被删除。</li><li style=\"text-align: justify;\"><strong>更新/通知机制</strong>：由IETF制定的 RFC2136 标准。<br>  如果中途域名主机改变IP地址，整个网络可能都不知道真正的IP地址，直到TTL到时，所以需要更新/通知机制。</li></ul><h3 style=\"text-align: justify; line-height: 1.5;\">DNS记录和消息</h3><h4 style=\"text-align: justify; line-height: 1.5;\">DNS记录</h4><p style=\"text-align: justify;\">  DNS的分布式数据库里存储了<strong>资源记录</strong>（resource record, RR）</p><p style=\"text-align: justify;\">RR的格式：<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>(name, value, type, ttl)</code></span></p><p style=\"text-align: justify;\"><strong>type = A</strong></p><ul><li style=\"text-align: justify;\">name：主机名</li><li style=\"text-align: justify;\">value：对应的IP地址</li></ul><p style=\"text-align: justify;\"><strong>type = NS</strong></p><ul><li style=\"text-align: justify;\">name：域（如<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>foo.com</code></span>）</li><li style=\"text-align: justify;\">value：对应的权威域名服务器的主机名</li></ul><p style=\"text-align: justify;\"><strong>type = CNAME</strong></p><ul><li style=\"text-align: justify;\">name：别名</li><li style=\"text-align: justify;\">value：对应的规范主机名</li><li style=\"text-align: justify;\">比如 <span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>www.ibm.com</code></span> 是 <span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>servereast.backup2.ibm.com</code></span> 的别名，这与负荷的分配有关，可能有多个服务器。</li></ul><p style=\"text-align: justify;\"><strong>type = MX</strong></p><ul><li style=\"text-align: justify;\">name：邮件服务器别名</li><li style=\"text-align: justify;\">value：对应的规范主机名</li></ul><h4 style=\"text-align: justify; line-height: 1.5;\">DNS消息</h4><p style=\"text-align: justify;\">  DNS有两种消息类型：查询（query）和回答（reply），两种消息格式相同。</p><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Network_DNS-message.png\" alt=\"DNS message.png\" data-href=\"\" style=\"width: 603.60px;height: 233.13px;\"></p><h4 style=\"text-align: justify; line-height: 1.5;\">向DNS数据库插入记录</h4><p style=\"text-align: justify;\">比如要创建一个<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>networkutopia.com</code></span>的网站</p><ul><li style=\"text-align: justify;\">先在<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>.com</code></span>的TLD提供商 Network Solution 注册 <span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>networkutopia.com</code></span></li><li style=\"text-align: justify;\">在自己的权威域名服务器上进行配置</li></ul><h3 style=\"text-align: justify; line-height: 1.5;\">DNS查询工具</h3><p style=\"text-align: justify;\">  在命令行用<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>nslookup</code></span>进行DNS查询。</p><h4 style=\"text-align: justify; line-height: 1.5;\">nslookup直接查询</h4><p style=\"text-align: justify;\">  查询一个域名的A记录，如果没指定dns-server，用系统默认的dns服务器。</p><p style=\"text-align: justify;\"><br></p><table style=\"width: auto;\"><tbody><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">1</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">nslookup domain [dns-server]<br></td></tr></tbody></table><h4 style=\"text-align: justify; line-height: 1.5;\">nslookup查询其他记录</h4><p><br></p><table style=\"width: auto;\"><tbody><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">1</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">nslookup -qt=type domain [dns-server]<br></td></tr></tbody></table><p style=\"text-align: justify;\">type可以是以下这些类型：</p><p style=\"text-align: justify;\"><br></p><table style=\"width: auto;\"><tbody><tr><th colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">type</th><th colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">类型</th></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">A</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">地址记录</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">AAAA</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">地址记录</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">AFSDB</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">Andrew文件系统数据库服务器记录</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">ATMA</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">ATM地址记录</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">CNAME</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">别名记录</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">HINFO</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">硬件配置记录，包括CPU、操作系统信息</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">ISDN</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">域名对应的ISDN号码</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">MB</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">存放指定邮箱的服务器</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">MG</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">邮件组记录</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">MINFO</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">邮件组和邮箱的信息记录</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">MR</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">改名的邮箱记录</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">MX</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">邮件服务器记录</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">NS</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">名字服务器记录</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">PTR</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">反向记录</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">RP</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">负责人记录</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">RT</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">路由穿透记录</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">SRV</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">TCP服务器信息记录</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">TXT</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">域名对应的文本信息</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">X25</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">域名对应的X.25地址记录</td></tr></tbody></table><p><br></p>', '', 7, 0, '2024-07-17 09:16:46.237', '2024-07-17 14:11:56.468');
INSERT INTO `articles` (`id`, `user_id`, `category_id`, `title`, `content`, `head_image`, `read_cnt`, `status`, `created_at`, `updated_at`) VALUES (9, 4, 3, '传输层（Transport Layer）', '<h2 style=\"text-align: justify; line-height: 1.5;\">传输层服务</h2><h3 style=\"text-align: justify; line-height: 1.5;\">传输层概述</h3><ul><li style=\"text-align: justify;\">为不同主机之间的应用进程提供通信的桥梁</li><li style=\"text-align: justify;\">端对端：传输层协议在端系统间运行，不需要涉及网络核心</li><li style=\"text-align: justify;\">传输层的协议：TCP和UDP</li></ul><p style=\"text-align: justify;\"><strong>传输层和网络层对比</strong></p><ul><li style=\"text-align: justify;\">网络层：主机之间的通信</li><li style=\"text-align: justify;\">传输层：进程之间的通信传输层依赖于并能强化网络层服务。</li></ul><h3 style=\"text-align: justify; line-height: 1.5;\">传输层协议</h3><ul><li style=\"text-align: justify;\">TCP：可靠的，有序的传送</li><li style=\"text-align: justify;\">UDP：不可靠的，无序的传送提供尽力而为交付服务二者均不提供的服务：延时保障、带宽保障</li></ul>', '', 4, 0, '2024-07-17 09:29:35.825', '2024-07-17 14:12:02.093');
INSERT INTO `articles` (`id`, `user_id`, `category_id`, `title`, `content`, `head_image`, `read_cnt`, `status`, `created_at`, `updated_at`) VALUES (10, 4, 3, '多路复用（Multiplexing）与多路分用（Demultiplexing）', '<h2 style=\"text-align: justify; line-height: 1.5;\">多路复用（Multiplexing）与多路分用（Demultiplexing）</h2><p style=\"text-align: justify;\">  多路复用存在于发送方：发送方需要处理多个套接字，并且给套接字加上传输层的头部。</p><p style=\"text-align: justify;\">  多路分用存在于接收方：利用头部信息，将接收到的报文段传输给正确的套接字。</p><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Network_Multiplexing.png\" alt=\"Multiplexing/demultiplexing.png\" data-href=\"\" style=\"\"></p><h3 style=\"text-align: justify; line-height: 1.5;\">多路分用</h3><h4 style=\"text-align: justify; line-height: 1.5;\">多路分用工作流程</h4><ul><li style=\"text-align: justify;\">主机收到IP数据报（IP datagram）</li><li style=\"text-align: justify;\">主机利用IP地址和端口号来把报文段传入正确的套接字</li></ul><h4 style=\"text-align: justify; line-height: 1.5;\">无连接的多路分用（Connectionless demultiplexing）</h4><p style=\"text-align: justify;\">  参考<a href=\"https://gy23333.github.io/2020/03/16/%E3%80%8A%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BD%91%E7%BB%9C-%E8%87%AA%E9%A1%B6%E5%90%91%E4%B8%8B%E6%96%B9%E6%B3%95%E3%80%8B%E7%AC%94%E8%AE%B0/#UDP%E4%B8%AD%E7%9A%84socket%E7%BC%96%E7%A8%8B\" target=\"\">UDP的socket工作方式</a>，如果数据报的<strong>目的IP地址和端口号</strong>相同，它们将被传到同一个socket当中。（即使数据报的源可能不同）</p><h4 style=\"text-align: justify; line-height: 1.5;\">面向连接的多路分用（Connection-oriented demux）</h4><p style=\"text-align: justify;\">  参考<a href=\"https://gy23333.github.io/2020/03/16/%E3%80%8A%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BD%91%E7%BB%9C-%E8%87%AA%E9%A1%B6%E5%90%91%E4%B8%8B%E6%96%B9%E6%B3%95%E3%80%8B%E7%AC%94%E8%AE%B0/#TCP%E4%B8%AD%E7%9A%84socket%E7%BC%96%E7%A8%8B\" target=\"\">TCP的socket工作方式</a></p><ul><li style=\"text-align: justify;\">标记TCP的socket需要4元组：源IP地址、源端口号、目的IP地址、目的端口号</li><li style=\"text-align: justify;\">多路分用：接收方要用到上面4个值来传入不同的socket</li><li style=\"text-align: justify;\">服务器的主机可能要同时支持多个TCP连接</li><li style=\"text-align: justify;\">web服务器有不同的socket对应每个连接的客户机，其中非持久性HTTP会给每个请求都建立新的socket。</li></ul><p style=\"text-align: justify;\"><br></p>', '', 4, 0, '2024-07-17 09:30:34.435', '2024-07-17 14:12:06.166');
INSERT INTO `articles` (`id`, `user_id`, `category_id`, `title`, `content`, `head_image`, `read_cnt`, `status`, `created_at`, `updated_at`) VALUES (11, 4, 3, '因特网中的路由选择', '<h2 style=\"text-align: justify; line-height: 1.5;\">因特网中的路由选择</h2><p style=\"text-align: justify;\">  内部网关协议（Interior Gateway Protocols，IGP）是AS内的路由。</p><p style=\"text-align: justify;\">常用的IGP有：</p><ul><li style=\"text-align: justify;\">RIP：路由信息协议，Routing Information Protocol</li><li style=\"text-align: justify;\">OSPF：开放最短路径，Open Shortest Path First</li><li style=\"text-align: justify;\">IGRP：Interior Gateway Routing Protocol</li></ul><h3 style=\"text-align: justify; line-height: 1.5;\">RIP：路由信息协议（Routing Information Protocol）</h3><ul><li style=\"text-align: justify;\">DV算法</li><li style=\"text-align: justify;\">cost：跳数 最大15跳，16跳视为∞∞。设置最大跳数以防止无穷计数问题，但这也限制了只能用于小网络，大网络很容易超最大跳数。</li><li style=\"text-align: justify;\">每30s通过发送通告的方式更新DV，通告最多路由到25个目的</li><li style=\"text-align: justify;\">如果超过180s每收到通告，则这个邻居/链路宣告死亡通过该邻居的路由失效发送新通告给邻居如果邻居的转发表变化，它也会发送新的通告链接失败的信息会快速迭代完成采用毒性逆转防止循环将16跳设置为∞∞</li><li style=\"text-align: justify;\">RIP运行在应用层（路由器实际可能存在应用层，只是不对用户开放）</li><li style=\"text-align: justify;\">通告用 UDP pkt 周期性发送</li></ul><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Network_RIP.png\" alt=\"\" data-href=\"\" style=\"width: 50%;\"></p><h3 style=\"text-align: justify; line-height: 1.5;\">OSPF：开放最短路径（Open Shortest Path First）</h3><h4 style=\"text-align: justify; line-height: 1.5;\">OSPF概述</h4><ul><li style=\"text-align: justify;\">对公众开放</li><li style=\"text-align: justify;\">使用<strong>LS算法</strong></li><li style=\"text-align: justify;\">OSPF通告每个邻居路由器携带一个条目</li><li style=\"text-align: justify;\">通告通过洪泛散布到整个AS</li></ul><h4 style=\"text-align: justify; line-height: 1.5;\">OSPF优点</h4><ul><li style=\"text-align: justify;\"><strong>安全</strong>：所有OSPF消息都要认证，防止恶意侵入</li><li style=\"text-align: justify;\"><strong>多条相同cost的路径</strong>：当到达某目的的多条路径具有相同的cost时，OSPF允许使用多条路径。即可以分流。</li><li style=\"text-align: justify;\"><strong>每条链路，给不同的数据类型不同的cost度量</strong></li><li style=\"text-align: justify;\"><strong>对单播和多播（MOSPF）路由的支持</strong>：对单播进行扩展，以便提供给多播使用</li><li style=\"text-align: justify;\"><strong>在大域中用分层OSPF</strong></li></ul><h4 style=\"text-align: justify; line-height: 1.5;\">分层OSPF</h4><ul><li style=\"text-align: justify;\">两层结构：<strong>局部区域</strong>（local area）和 <strong>主干</strong>（backbone）</li><li style=\"text-align: justify;\"><strong>区域边界路由器</strong>（area border router）：负责为流向该区域以外的分组提供路由选择。汇拢该区域的节点距离信息，通告给其他的区域边界路由器</li><li style=\"text-align: justify;\"><strong>主干路由器</strong>（backbone router）：在主干内运行OSPF路由</li><li style=\"text-align: justify;\"><strong>网关路由器</strong>（boundary router）：与其他AS连接</li></ul><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Network_Hierarchical-OSPF.png\" alt=\"\" data-href=\"\" style=\"width: 50%;\"></p><h3 style=\"text-align: justify; line-height: 1.5;\">IGRP（Interior Gateway Routing Protocol）</h3><ul><li style=\"text-align: justify;\">最初是CISCO私有的，后来开放了，RIP的后继者</li><li style=\"text-align: justify;\">DV算法</li><li style=\"text-align: justify;\">cost：时延、带宽、可靠性、负荷等等</li><li style=\"text-align: justify;\">利用TCP来交换路由更新</li><li style=\"text-align: justify;\">利用<strong>扩散更新算法</strong>（Diffusing Update Algorithm,DUAL）来防止循环</li></ul><h3 style=\"text-align: justify; line-height: 1.5;\">BGP：边界网管协议（Border Gateway Protocol）</h3><h4 style=\"text-align: justify; line-height: 1.5;\">BGP概述</h4><p style=\"text-align: justify;\">采用 <strong>Path Vector protocol</strong></p><ul><li style=\"text-align: justify;\">与<strong>DV协议</strong>相似</li><li style=\"text-align: justify;\">每个边界网关向邻居（对等方）广播到达目的地的整个路径（即 AS的序列）</li><li style=\"text-align: justify;\">eBGP：外部BGP，跨越两个AS对话。从相邻的AS获取子网可达性信息。</li><li style=\"text-align: justify;\"><strong>iBGP</strong>：内部BGP，同一个AS中的两台路由器之间的BGP对话。将可达性信息传播到所有内部AS路由器。</li></ul><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Network_eBGP-iBGP.png\" alt=\"\" data-href=\"\" style=\"\"></p><ul><li style=\"text-align: justify;\">BGP会话：两BGP路由器通过半永久的TCP连接来交换消息</li><li style=\"text-align: justify;\">如果一个AS向另一个AS通告了某个路由器，则承诺了可以路由到该路由器</li></ul><h4 style=\"text-align: justify; line-height: 1.5;\">路径属性和BGP路由</h4><ul><li style=\"text-align: justify;\">通告前缀（advertised prefix）包括BGP属性</li><li style=\"text-align: justify;\">两个重要attributes</li><li style=\"text-align: justify;\">基于policy的路由</li></ul><h4 style=\"text-align: justify; line-height: 1.5;\">BGP消息</h4><ul><li style=\"text-align: justify;\">使用TCP交换BGP消息</li><li style=\"text-align: justify;\">BGP消息：</li></ul><h4 style=\"text-align: justify; line-height: 1.5;\">BGP路由选择</h4><p style=\"text-align: justify;\">  路由器可能知道到达同一个前缀的多条路由。BGP以下优先级选择路由：</p><ul><li style=\"text-align: justify;\">本地偏好值：由政策决定</li><li style=\"text-align: justify;\">最短 AS-PATH：通过的AS最少</li><li style=\"text-align: justify;\">最近 NEXT-HOP 路由器：最近的下一跳路由器</li><li style=\"text-align: justify;\">其他标准</li></ul><p style=\"text-align: justify;\">假设：网关X 将其路径发送到 网关W</p><ul><li style=\"text-align: justify;\">W 可以选择/不选 X所提供的路径</li><li style=\"text-align: justify;\">如果W选择X通告的路径</li><li style=\"text-align: justify;\">X可以通过advertisement来控制传入流量：</li></ul><h4 style=\"text-align: justify; line-height: 1.5;\">BGP路由策略</h4><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Network_BGP-policy.png\" alt=\"\" data-href=\"\" style=\"\"></p><ul><li style=\"text-align: justify;\">A,B,C是ISP（网络服务提供商）</li><li style=\"text-align: justify;\">W,X,Y是客户</li><li style=\"text-align: justify;\">X是 Multihomed AS，连接了两个ISP，也可以称为 dual-homed，一般是大型公司。X可以不允许 B -&gt; X -&gt; C 这条路由，则X不通告B有路由到C</li><li style=\"text-align: justify;\">A 通告 B 路径 AW</li><li style=\"text-align: justify;\">B 通告 X 路径 BAW</li><li style=\"text-align: justify;\">是否 B 通告 C 路径 BAW ？</li></ul><h4 style=\"text-align: justify; line-height: 1.5;\">Inra-/Inter-AS 的区别</h4><p style=\"text-align: justify;\"><strong>规模</strong>：分层可以节省表格大小，减小更新的流量。</p><p style=\"text-align: justify;\"><br></p><table style=\"width: auto;\"><tbody><tr><th colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\"></th><th colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">Intra-AS</th><th colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">Inter-AS</th></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\"><strong>Policy</strong></td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">一个管理员，不需要policy决策</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">管理员想要控制路由，需要有policy</td></tr><tr><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\"><strong>性能</strong></td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">关注性能</td><td colspan=\"1\" rowspan=\"1\" width=\"auto\" style=\"text-align: left;\">比起性能更关注policy</td></tr></tbody></table><p><br></p>', '', 8, 0, '2024-07-17 09:34:55.765', '2024-07-17 14:12:09.663');
INSERT INTO `articles` (`id`, `user_id`, `category_id`, `title`, `content`, `head_image`, `read_cnt`, `status`, `created_at`, `updated_at`) VALUES (12, 1, 4, '操作系统基本概念', '<h2 style=\"text-align: left;\">操作系统基本概念</h2><ul><li style=\"text-align: left;\">操作系统定义：​ 操作系统是指控制和管理整个计算机系统的硬件与软件资源，合理地组织、调度计算机的工作与资源的分配，进而为用户和其他软件提供方便接口与环境的程序集合。操作系统是计算机系统中最基本的系统软件。</li><li style=\"text-align: left;\">操作系统的基本特征：并发：并发是指两个或多个事件在同一时间间隔内发生。操作系统的并发性是指计算机系统中同时存在多个运行的程序，因此它具有处理和调度多个程序同时执行的能力。引入进程的目的是使程序能并发执行。注意同一时间间隔（并发）和同一时刻（并行）的区别：并发：在多道程序环境下，一段时间内，宏观上有多道程序在同时执行。而在每个时刻，单处理机环境下实际仅能有一道程序执行。因此微观上这些程序仍是分时交替执行的。操作系统的并发性是通过分时得以实现的。并行：并行性是指系统具有同时进行运算或操作的特性，在同一时刻能完成两种或两种以上的工作。并行性需要有相关硬件的支持，如多流水线或多处理机硬件环境。共享：​ 共享是指系统中的资源可供内存中多个并发执行的进程共同使用，分为两类：互斥共享方式：​ 仅当进程 A 访问完并释放该资源后，才允许另一个进程 B 对该资源进行访问。即在一段时间内只允许一个进程访问该资源，这种资源称为临界资源或独占资源。同时访问方式：​ 宏观上在一段时间内允许多个进程「同时」访问某些资源，微观上「轮流」（交替）访问。同时访问的典型资源是磁盘设备。操作系统最基本的特征是并发和共享，两者互为存在条件。虚拟：​ 虚拟是指把一个物理上的实体变为若干逻辑上的对应物，有以下应用：时分复用技术：​ 虚拟处理器技术是通过多道程序设计技术，采用让多道程序并发执行的方法，来分时使用一个处理器的。空分复用技术：​ 虚拟存储器技术将一台机器的物理存储器变为虚拟存储器，以便从逻辑上扩充存储器的容量。异步：​ 多道程序环境允许多个程序并发执行，但由于资源有限（资源竞争），进程的执行以不可预知的速度向前推进，这就是进程的异步性。</li><li style=\"text-align: left;\">操作系统作为计算机系统资源的管理者的功能：处理机管理：在多道程序环境下，处理机的分配和运行都以进程（或线程）为基本单位，因而对处理机的管理可归结为对进程的管理。并发是指在计算机内同时运行多个进程，因此进程何时创建、何时撤销、如何管理、如何避免冲突、合理共享就是进程管理的最主要的任务。进程管理的主要功能包括进程控制、进程同步、进程通信、死锁处理、处理机调度等。存储器管理：存储器管理是为了给多道程序的运行提供良好的环境，方便用户使用及提高内存的利用率。主要包括内存分配与回收、地址映射、内存保护与共享和内存扩充等功能。文件管理：计算机中的信息都是以文件的形式存在的，操作系统中负责文件管理的部分称为文件系统。文件管理包括文件存储空间的管理、目录管理及文件读写管理和保护等，但不关心文件具体内容，如：源代码、编译器。设备管理：设备管理的主要任务是完成用户的 I/O 请求，方便用户使用各种设备，并提高设备的利用率。主要包括缓冲管理、设备分配、设备处理和虚拟设备等功能。</li><li style=\"text-align: left;\">操作系统作为用户与计算机硬件系统之间的接口（了解）：命令接口：​ 用户利用这些操作命令来组织和控制作业的执行，分为两类：联机命令接口：​ 「雇主」说一句话，「工人」做一件事，并做出反馈，这就强调了交互性。脱机命令接口：​ 「雇主」把要「工人」做 的事写在清单上，「工人」按照清单命令逐条完成这些事。用户不能直接干预作业的运行。程序接口：​ 程序接口由一组系统调用（也称广义指令）组成。用户通过在程序中使用这些系统调用来请求操作系统为其提供服务，如使用各种外部设备、申请分配和回收内存及其他各种要求。当前最为流行的是图形用户界面（GUI），即图形接口。GUI 最终是通过调用程序接口实现的，所调用的系统调用命令是操作系统的一部分。</li></ul><h2 style=\"text-align: left;\">操作系统的发展与分类（理解）</h2><ol><li style=\"text-align: left;\">手工操作阶段（此阶段无操作系统）：用户在计算机上算题的所有工作都要人工干预，如程序的装入、运行、结果的输出等。随着计算机硬件的发展，人机矛盾（速度和资源利用）越来越大</li><li style=\"text-align: left;\">批处理阶段（操作系统开始出现）：批处理系统是实现作业自动控制而无须人工干预的系统。单道批处理系统：系统对作业的处理是成批进行的，但内存中始终保持一道作业。目的是为了解决人机矛盾及 CPU 和 I/O 设备速率不匹配的矛盾主要特征：自动性：​ 在顺利的情况下，磁带上的一批作业能自动地逐个运行，而无须人工干预。顺序性：​ 磁带上的各道作业顺序地进入内存，各道作业的完成顺序与它们进入内存的顺序在正常情况下应完全相同。单道性：​ 内存中仅有一道程序运行，即监督程序每次从磁带上只调入一道程序进入内存。多道批处理系统：多道程序设计技术允许多个程序同时进入内存并允许它们在 CPU 中交替地运行，这些程序共享系统中的各种硬/软件资源。多道程序设计的特点：多道：​ 计算机内存中同时存放多道相互独立的程序。宏观上并行：​ 同时进入系统的多道程序都处于运行过程中，即它们先后开始各自的运行，但都未运行完毕。微观上串行：​ 内存中的多道程序轮流占有 CPU，交替执行。优点：资源利用率高，多道程序共享计算机资源，从而使各种资源得到充分利用。系统吞吐量大，CPU 和其他资源保持「忙碌」状态。缺点：用户响应的时间较长。不提供人机交互能力，用户既不能了解自己的程序的运行情况，又不能控制计算机。</li><li style=\"text-align: left;\">分时操作系统：分时技术指把处理器的运行时间分成很短的时间片，按时间片轮流把 CPU 分配给各联机作业使用。若某个作业在分配给它的时间片内不能完成其计算，则该作业暂时停止运行，把处理器让给其他作业使用，等待下一轮再继续运行。由于计算机速度很快，作业运行轮转得也很快，因此给每个用户的感觉就像是自己独占一台计算机。多道批处理是实现作业自动控制而无须人工干预的系统，而分时系统是实现人机交互的系统。分时系统的主要特征如下：同时性（多路性）：​ 指允许多个终端用户同时使用一台计算机，即一台计算机与若干台终端相连接，终端上的这些用户可以同时或基本同时使用计算机。交互性：​ 用户能够方便地与系统进行人机对话，即用户通过终端采用人机对话的方式直接控制程序运行，与同程序进行交互。独立性：​ 系统中多个用户可以彼此独立地进行操作，互不干扰，单个用户感觉不到别人 也在使用这台计算机，好像只有自己单独使用这台计算机一样。及时性：​ 用户请求能在很短时间内获得响应。分时系统采用时间片轮转方式使一台计算机同时为多个终端服务，使用户能够对系统的及时响应感到满意。</li><li style=\"text-align: left;\">实时操作系统：为了能在某个时间限制内完成某些紧急任务而不需要时间片排队，诞生了实时操作系统。这里的时间限制可以分为两种情况：若某个动作必须绝对地在规定的时刻（或规定的时间范围）发生，则称为硬实时系统，如飞行器的飞行自动控制系统，这类系统必须提供绝对保证，让某个特定的动作在规定的时间内完成。若能够接受偶尔违反时间规定且不会引起任何永久性的损害，则称为软实时系统，如飞机订票系统、银行管理系统。在实时操作系统的控制下，计算机系统接收到外部信号后及时进行处理，并在严格的时限内处理完接收的事件。实时系统必须能足够及时地处理某些紧急的外部事件，因此普遍用高优先级，并用「可抢占」来确保实时处理。实时操作系统的主要特点是及时性和可靠性，允许以「浪费」一些资源为代价。</li><li style=\"text-align: left;\">网络操作系统和分布式计算机系统</li><li style=\"text-align: left;\">个人计算机操作系统</li></ol><h2 style=\"text-align: left;\">操作系统运行环境</h2><h3 style=\"text-align: left;\">内核态和用户态</h3><ul><li style=\"text-align: left;\">计算机系统中，通常 CPU 执行两种不同性质的程序：操作系统内核程序用户自编程序（ 简称「应用程序」）前者是后者的管理者</li><li style=\"text-align: left;\">因此「管理程序」（即内核程序）可以执行一些特权指令，而「被管理程序」（即用户自编程序）出于安全考虑不能执行这些指令。</li><li style=\"text-align: left;\">特权指令是指计算机中不允许用户直接使用的指令，如 I/O 指令，置中断指令，存取用于内存保护的寄存器，送程序状态字到程序状态字寄存器等的指令。</li><li style=\"text-align: left;\">在具体实现上，将 CPU 的状态划分为用户态（目态）和核心态（又称管态、内核态）。</li><li style=\"text-align: left;\">操作系统的内核构成：与硬件关联较紧密的模块，如时钟管理、中断处理、设备驱动等处于最低层与运行频率较高的程序，如进程管理、存储器管理和设备管理。这两部分内容的指令操作工作在核心态。注意选择题中「执行」和「发生」的区别。</li><li style=\"text-align: left;\">操作系统的内核的内容：时钟管理：在计算机的各种部件中，时钟是最关键的设备。时钟的第一功能是计时。第二功能是通过时钟中断的管理，可以实现进程的切换。例如：在分时操作系统中采用时间片轮转调度，在实时系统中按截止时间控制运行。在批处理系统中通过时钟管理来衡量一个作业的运行程度。中断机制：引入中断技术的初衷是提高多道程序运行环境中 CPU 的利用率，而且主要是针对外部设备的。后来逐步成为操作系统各项操作的基础。例如，键盘或鼠标信息的输入、进程的管理和调度、系统功能的调用、设备驱动、文件访问等。可以说，现代操作系统是靠中断驱动的软件。中断机制中，只有一小部分功能属于内核，它们负责保护和恢复中断现场的信息，转移控制权到相关的处理程序。这样可以减少中断的处理时间，提高系统的并行处理能力。原语：原语定义：​ 按层次结构设计的操作系统，底层是一些可被调用的公用小程序，它们各自完成一个规定的操作，特点如下：处于操作系统的最低层，是最接近硬件的部分。这些程序的运行具有原子性，其操作只能一气呵成（主要从系统安全性和便于管理考虑）。这些程序的运行时间都较短，而且调用频繁。通常把具有这些特点的程序称为原语（Atomic Operation）。定义原语的直接方法是关闭中断，让其所有动作不可分割地完成后再打开中断。系统中的设备驱动、CPU 切换、进程通信等功能中的部分操作都可定义为原语，使它们成为内核的组成部分。系统控制的数据结构及处理：​ 系统中用来登记状态信息的数据结构很多，如作业控制块、进程控制块（PCB）、设备控制块、各类链表、消息队列、缓冲区、空闲区登记表、内存分配表等。为了实现有效的管理，系统需要一些基本的操作，常见的操作有以下 3 种：进程管理：​ 进程状态管理、进程调度和分派、创建与撤销进程控制块等。存储器管理：​ 存储器的空间分配和回收、内存信息保护程序、代码对换程序等。设备管理：​ 缓冲区管理、设备分配和回收等。核心态指令实际上包括系统调用类指令和一些针对时钟、中断和原语的操作指令。</li></ul><h3 style=\"text-align: left;\">中断</h3><ul><li style=\"text-align: left;\">中断（外中断）和异常（内中断）概念：系统不允许用户程序实现核心态的功能，而它们又必须使用这些功能，就得通过中断或异常实现。中断（Interruption）也称外中断，指来自 CPU 执行指令以外的事件的发生，如外设请求或人为干预。异常（Exception）也称内中断、例外或陷入（trap），指源自 CPU 执行指令内部的事件，如程序的非法操作码地址越界、算术溢出、虚存系统的缺页及专门的陷入指令等引起的事件。对异常的处理一般要依赖于当前程序的运行现场，而且异常不能被屏蔽，一旦出现应立即处理。所谓「缺页中断」属于异常，在考研题中，认为『「访存时缺页」属于中断』这句话是错误的。</li><li style=\"text-align: left;\">中断处理过程：关中断：CPU 响应中断后，首先要保护程序的现场状态，在保护现场的过程中，CPU 不应响应更高级中断源的中断请求。若现场保存不完整，在中断服务程序结束后，也就不能正确地恢复并继续执行现行程序。保存断点：​ 为保证中断服务程序执行完毕后能正确地返回到原来的程序，必须将原来的程序的断点（即程序计数器 PC）保存起来。中断服务程序寻址：​ 其实质是取出中断服务程序的入口地址送入程序计数器 PC。上面三步是在 CPU 进入中断周期后，由硬件自动（中断隐指令）完成的。下面几步由中断服务程序完成。保存现场和屏蔽字：​ 进入中断服务程序后，首先要保存现场，现场信息一般是指程序状态字寄存器 PSWR 和某些通用寄存器的内容。开中断：​ 允许更高级中断请求得到响应。执行中断服务程序：​ 这是中断请求的目的。关中断：​ 保证在恢复现场和屏蔽字时不被中断。恢复现场和屏蔽字：​ 将现场和屏蔽字恢复到原来的状态。开中断、中断返回：​ 中断服务程序的最后一条指令通常是一条中断返回指令，使其返回到原程序的断点处，以便继续执行原程序。​ 易错点：​ 由硬件自动保存被中断程序的断点（即程序计数器 PC）。</li></ul><h3 style=\"text-align: left;\">系统调用</h3><ul><li style=\"text-align: left;\">系统调用是指用户在程序中调用操作系统所提供的一些子功能，系统调用可视为特殊的公共子程序。</li><li style=\"text-align: left;\">系统中的各种共享资源都由操作系统统一掌管，因此在用户程序中，凡是与资源有关的操作（如存储分配、进行 I/O 传输及管理文件等），都必须通过系统调用方式向操作系统提出服务请求，并由操作系统代为完成。</li><li style=\"text-align: left;\">这些系统调用按功能大致可分为如下几类。设备管理：​ 完成设备的请求或释放，以及设备启动等功能。文件管理：​ 完成文件的读、写、创建及删除等功能。进程控制：​ 完成进程的创建、撤销、阻塞及唤醒等功能。进程通信：​ 完成进程之间的消息传递或信号传递等功能。内存管理：​ 完成内存的分配、回收以及获取作业占用内存区大小及始址等功能。</li></ul><blockquote style=\"text-align: left;\">操作系统的运行环境就可以理解为：用户通过操作系统运行上层程序（如系统提供的命令解释程序或用户自编程序），而这个上层程序的运行依赖于操作系统的底层管理程序提供服务支持。当需要管理程序服务时，系统则通过硬件中断机制进入核心态，运行管理程序当程序运行出现异常情况时，也会被动地需要管理程序的服务，这时就通过异常处理来进入核心态（trap 指令在用户态执行）。管理程序运行结束时，用户程序需要继续运行，此时通过相应的保存的程序现场，退出中断处理程序或异常处理程序，返回断点处继续执行。一些由用户态转向核心态的例子： + 用户程序要求操作系统的服务，即系统调用。 + 发生一次中断。 + 用户程序中产生了一个错误状态。 + 用户程序中企图执行一条特权指令（需要访管中断，访管指令不是特权指令）。 + 从核心态转向用户态由一条指令实现，这条指令是特权命令，一般是中断返回指令。执行系统调用的过程如下：正在运行的进程先传递系统调用参数在用户态执行陷入指令，将用户态转换为内核态，并将返回地址压入堆栈以备后用CPU 执行相应的内核态服务程序最后返回用户态</blockquote><h2 style=\"text-align: left;\">大内核（宏内核）和微内核</h2><ul><li style=\"text-align: left;\"><strong>大内核</strong>系统将操作系统的<strong>主要功能模块</strong>都作为一个紧密联系的整体运行在<strong>核心态</strong>，从而为应用提供<strong>高性能</strong>的系统服务。</li><li style=\"text-align: left;\">因为各管理模块之间<strong>共享信息</strong>，能有效利用相互之间的有效特性，所以具有无可比拟的性能优势。</li><li style=\"text-align: left;\">为解决操作系统的内核代码难以维护的问题，提出了<strong>微内核</strong>的体系结构。它将内核中<strong>最基本的功能（如进程管理等）保留在内核</strong>，而将那些不需要在核心态执行的功能移到<strong>用户态</strong>执行，从而降低了内核的<strong>设计复杂性</strong>。</li><li style=\"text-align: left;\">那些移出内核的操作系统代码根据分层的原则被划分成若干服务程序，它们的执行相互独立，<strong>交互则都借助于微内核进行通信</strong>。</li><li style=\"text-align: left;\">微内核结构有效地分离了内核与服务、服务与服务，使得它们之间的接口更加清晰，维护的代价大大降低，各部分可以独立地优化和演进，从而保证了操作系统的<strong>可靠性</strong>。</li><li style=\"text-align: left;\">微内核结构的最大问题是<strong>性能问题</strong>，因为需要频繁地在核心态和用户态之间进行切换，操作系统的执行开销偏大。</li></ul>', '/images/image_20240717141102.png', 1, 0, '2024-07-17 14:11:04.435', '2024-07-17 14:27:51.579');
INSERT INTO `articles` (`id`, `user_id`, `category_id`, `title`, `content`, `head_image`, `read_cnt`, `status`, `created_at`, `updated_at`) VALUES (13, 4, 3, '应用层（Application Layer）——Web和HTTP', '<h2 style=\"text-align: justify; line-height: 1.5;\">Web和HTTP</h2><p style=\"text-align: justify;\">​ World Wide Web 中的网页由超链接（hyperlink）连接。</p><ul><li style=\"text-align: justify;\">页面由很多对象（object）组成，对象存储在服务器中；</li><li style=\"text-align: justify;\">对象有多种类型，可以是HTML文件，JPEG图片，动态脚本等等；</li><li style=\"text-align: justify;\">网页以HTML文件为基础，包括了许多参考对象，每个对象都可以通过URL来寻址。例如一张图片的URL为<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>www.someshcool.edu/someDept/pic.gif</code></span>，其中<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>www.someshcool.edu</code></span>为主机名，<span style=\"color: rgb(85, 85, 85); background-color: rgb(238, 238, 238);\"><code>/someDept/pic.gif</code></span>为路径名。</li></ul><h3 style=\"text-align: justify; line-height: 1.5;\">HTTP概述</h3><p style=\"text-align: justify;\">​ 超文本传输协议（hypertext transfer protocol, HTTP）</p><ul><li style=\"text-align: justify;\">网页的应用层协议</li><li style=\"text-align: justify;\">基于客户机-服务器体系结构客户机：负责请求、接收和显示Web对象服务器：Web服务器负责发送对象，响应客户机请求</li><li style=\"text-align: justify;\">HTTP的传输层使用<strong>TCP</strong></li><li style=\"text-align: justify;\">HTTP是无状态的<br>​   服务器不会保留之前客户机发的请求信息。<br>​   协议要维持状态是很复杂的：保留之前的历史记录很消耗资源；如果客户机或着服务器有死机，它们的状态会不一致，还需要重新同步，这很麻烦。</li><li style=\"text-align: justify;\">HTTP消息类型：请求（request）与响应（response）</li></ul><h3 style=\"text-align: justify; line-height: 1.5;\">HTTP连接类型</h3><h4 style=\"text-align: justify; line-height: 1.5;\">非持久性连接（Non-persistent HTTP）</h4><h5 style=\"text-align: justify; line-height: 1.5;\">非持久性HTTP步骤</h5><ol><li style=\"text-align: justify;\">TCP连接开启</li><li style=\"text-align: justify;\">通过这个TCP连接最多传输一个对象</li><li style=\"text-align: justify;\">TCP连接关闭如果要加载多个对象时，需要多次非持久性HTTP连接。</li></ol><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Non-persistent%20HTTP(1).png\" alt=\"Non-persistent%20HTTP(1).png\" data-href=\"\" style=\"width: 805.80px;height: 403.40px;\"><br><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Non-persistent%20HTTP(2).png\" alt=\"Non-persistent%20HTTP(2).png\" data-href=\"\" style=\"width: 713.80px;height: 352.01px;\"></p><h5 style=\"text-align: justify; line-height: 1.5;\">非持久性HTTP响应时间</h5><p style=\"text-align: justify;\"><strong>RTT</strong>：往返时间（Round Trip Time）,一个很小的数据包（处理文件的时间可忽略）从客户机传到服务器再传回来的时间。</p><p style=\"text-align: justify;\"><strong>HTTP响应时间</strong>（一个对象）：</p><ul><li style=\"text-align: justify;\">1个RTT：建立TCP连接的时间</li><li style=\"text-align: justify;\">1个RTT：HTTP请求以及收到HTTP响应的前几个字符的时间</li><li style=\"text-align: justify;\">对象/文件传输的时间对一个对象来说，非持久性HTTP响应时间为</li></ul><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/NetWork%20Non-persistent%20HTTP%20response%20time.png\" alt=\"Non-persistent response time.png\" data-href=\"\" style=\"width: 571.00px;height: 525.67px;\"></p><p style=\"text-align: justify;\"><br></p><p>例题：如果一个网页包含1个HTML和10个对象，则非持久性HTTP响应需要多少时间？</p><h5 style=\"text-align: justify; line-height: 1.5;\">非持久性HTTP的问题</h5><ul><li style=\"text-align: justify;\">每传输一个对象都需要耗费 $2RTT$</li><li style=\"text-align: justify;\">每建立一个TCP连接都会对操作系统（OS）产生负荷</li><li style=\"text-align: justify;\">并行抓取：浏览器常常开多个并行的TCP连接去抓取对象</li><li style=\"text-align: justify;\"></li></ul><p>例题：一个网页包含1个HTML和10张图片，共有5个并行的TCP连接，则非持久性HTTP响应需要多少个RTT？<br>  首先传输HTML需要 $2RTT$ 的时间，5个并行的TCP连接传输10个对象需要2个 $2RTT$ 的时间。</p><h4 style=\"text-align: justify; line-height: 1.5;\">持久性连接（Persistent HTTP）</h4><h5 style=\"text-align: justify; line-height: 1.5;\">持久性HTTP步骤</h5><ol><li style=\"text-align: justify;\">开启TCP连接</li><li style=\"text-align: justify;\">通过这一个TCP连接可以传多个对象</li><li style=\"text-align: justify;\">TCP连接关闭</li></ol><h5 style=\"text-align: justify; line-height: 1.5;\">持久性HTTP特点（HTTP1.1）</h5><ul><li style=\"text-align: justify;\">服务器在发送响应后保持连接开启状态</li><li style=\"text-align: justify;\">后续这个客户机\\服务器的HTTP消息都通过该开启的连接发送</li><li style=\"text-align: justify;\">两种发送对象方式：HTTP1.1采用流水的方式发送：一次性把对象全发了；另一种是客户机接收到一个对象后接着发下一个对象的请求</li><li style=\"text-align: justify;\">至少需要1个RTT发完所有对象</li></ul>', '', 2, 0, '2024-07-17 14:13:12.940', '2024-07-17 14:16:41.664');
INSERT INTO `articles` (`id`, `user_id`, `category_id`, `title`, `content`, `head_image`, `read_cnt`, `status`, `created_at`, `updated_at`) VALUES (14, 4, 3, '网络层（Network Layer）——路由器工作原理', '<h2 style=\"text-align: justify; line-height: 1.5;\">路由器工作原理</h2><h3 style=\"text-align: justify; line-height: 1.5;\">路由器结构</h3><ul><li style=\"text-align: justify;\">输入端口（Input port）</li><li style=\"text-align: justify;\">交换结构（Switch fabric）</li><li style=\"text-align: justify;\">输出端口（Output port）</li><li style=\"text-align: justify;\">路由选择处理器（Routing processor）</li></ul><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Network_Router-architecture.png\" alt=\"Router architecture.png\" data-href=\"\" style=\"width: 822.80px;height: 403.30px;\"></p><ul><li style=\"text-align: justify;\">上半部分为控制面板：软件、毫秒级</li><li style=\"text-align: justify;\">下半部分为数据面板：硬件、纳秒级</li></ul><h4 style=\"text-align: justify; line-height: 1.5;\">输入端口（Input port）</h4><ol><li style=\"text-align: justify;\">线路端接（line termination）：物理层功能，用来比特的接收</li><li style=\"text-align: justify;\">数据链路处理（协议，拆封）（data link processing (protocol, decapsulation)）：数据链路层功能，比如以太网</li><li style=\"text-align: justify;\">查找、转发、排队（lookup, forwarding, queueing）</li></ol><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Network_Input-port-processing.png\" alt=\"Input port processing.png\" data-href=\"\" style=\"width: 838.80px;height: 221.72px;\"></p><h4 style=\"text-align: justify; line-height: 1.5;\">交换结构（Switch fabric）</h4><p style=\"text-align: justify;\">  三种交换结构：共享内存、共享总线、交叉开关矩阵</p><h5 style=\"text-align: justify; line-height: 1.5;\">共享内存（Switching via memory）</h5><ul><li style=\"text-align: justify;\">初代路由常采用共享内存</li><li style=\"text-align: justify;\">pkt在memory复制</li><li style=\"text-align: justify;\">速度被内存带宽限制，每个datagram都要经过2个bus</li><li style=\"text-align: justify;\">Cisco Catalyst 8500</li></ul><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Network_Switching-Memory.png\" alt=\"Switching via memory.png\" data-href=\"\" style=\"width: 552.00px;height: 229.68px;\"></p><h5 style=\"text-align: justify; line-height: 1.5;\">共享总线（Switching via a bus）</h5><ul><li style=\"text-align: justify;\">datagram通过共享的bus从输入端口到输出端口</li><li style=\"text-align: justify;\">总线冲突（bus contention）：交换速度被总线带宽限制</li><li style=\"text-align: justify;\">Cisco 5600</li></ul><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Network_Switching-Bus.png\" alt=\"Switching via a bus.png\" data-href=\"\" style=\"width: 472.00px;height: 366.04px;\"></p><h5 style=\"text-align: justify; line-height: 1.5;\">交叉开关矩阵（Switching via an interconnection network）</h5><ul><li style=\"text-align: justify;\">客服总线带宽的限制</li><li style=\"text-align: justify;\">纵横式交换机是一种由2N条总线组成的互联网络，连接N个输入端口和N个输出端口</li><li style=\"text-align: justify;\">可并行转发多个分组，但如果同输入输出端口，还是必须等待前一个发送了再发下一个</li><li style=\"text-align: justify;\">Cisco 12000</li></ul><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Network_Switching-Interconnection-Network.png\" alt=\"Switching via an interconnection network.png\" data-href=\"\" style=\"width: 427.00px;height: 465.81px;\"></p><h4 style=\"text-align: justify; line-height: 1.5;\">输出端口（Output port）</h4><ol><li style=\"text-align: justify;\">排队（缓存管理）（Queueing(datagram buffer)）</li><li style=\"text-align: justify;\">数据链路处理（协议，封装）（Data link processing(protocol, encapsulation)）</li><li style=\"text-align: justify;\">线路端接（Line termination）</li></ol><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Network_Output-port-processing.png\" alt=\"Output port processing.png\" data-href=\"\" style=\"width: 730.80px;height: 190.24px;\"></p><h3 style=\"text-align: justify; line-height: 1.5;\">排队</h3><h4 style=\"text-align: justify; line-height: 1.5;\">输入端口排队</h4><ul><li style=\"text-align: justify;\">当fabric比input port慢时，发生排队</li><li style=\"text-align: justify;\">buffer满时，出现排队延时和丢包</li><li style=\"text-align: justify;\">队首阻塞（Head-of-the-Line blocking，HOL）：队首的datagram会阻塞排在它后面的datagram输入</li></ul><h4 style=\"text-align: justify; line-height: 1.5;\">输出端口排队</h4><ul><li style=\"text-align: justify;\">当switch到达比output line快，发生排队</li><li style=\"text-align: justify;\">buffer满时，出现排队延时和丢包</li></ul>', '', 0, 0, '2024-07-17 14:14:46.264', '2024-07-17 14:14:46.264');
INSERT INTO `articles` (`id`, `user_id`, `category_id`, `title`, `content`, `head_image`, `read_cnt`, `status`, `created_at`, `updated_at`) VALUES (15, 4, 3, '链路层（Link Layer）——多路访问链路和协议', '<h2 style=\"text-align: justify; line-height: 1.5;\">多路访问链路和协议（Multiple Access Links and Protocols）</h2><p style=\"text-align: justify;\">链路的两种类型：</p><ul><li style=\"text-align: justify;\">点对点链路（point-to-point link） 由链路一端的单个发送方和链路另一端的单个接收方组成。</li><li style=\"text-align: justify;\">广播链路（broadcast link） 多个发送方和接收方，单一的、共享的信道。 多路访问协议（Multiple access protocol），规范结点在共享的广播信道上的传输行为。</li></ul><p style=\"text-align: justify;\">多路访问协议分类：</p><ul><li style=\"text-align: justify;\"><strong>信道划分协议</strong>（channel partitioning protocol）</li><li style=\"text-align: justify;\"><strong>随机接入协议</strong>（random access protocol）</li><li style=\"text-align: justify;\"><strong>轮流协议</strong>（taking-turns protocol）</li></ul><p style=\"text-align: justify;\">多路访问协议的目标：高效、公平、简单、分布式</p><h3 style=\"text-align: justify; line-height: 1.5;\">信道划分协议（Channel Partitioning protocols）</h3><h4 style=\"text-align: justify; line-height: 1.5;\">时分多路复用（TDMA）</h4><p style=\"text-align: justify;\">  TDM将时间划分为时间帧（frame），并进一步划分每个时间帧为$N$个时隙（slot），链路中的每条连接专用一个时隙。</p><h4 style=\"text-align: justify; line-height: 1.5;\">频分多路复用（FDMA）</h4><p style=\"text-align: justify;\">  链路中的每条连接专用一个频段。</p><h4 style=\"text-align: justify; line-height: 1.5;\">码分多址（CDMA）</h4><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Network_CDMA.png\" alt=\"\" data-href=\"\" style=\"width: 843.80px;height: 526.66px;\"></p><h3 style=\"text-align: justify; line-height: 1.5;\">随机接入协议（Random Access protocols）</h3><ul><li style=\"text-align: justify;\">结点传输pkt时，占有信道全部带宽，结点间无优先级</li><li style=\"text-align: justify;\">存在多个传输结点 =&gt; 碰撞</li><li style=\"text-align: justify;\">随机接入协议明确了：</li><li style=\"text-align: justify;\">常用的随机接入协议</li></ul><h4 style=\"text-align: justify; line-height: 1.5;\">纯ALOHA（Pure ALOHA）</h4><ul><li style=\"text-align: justify;\">非时隙、简单、完全分散</li><li style=\"text-align: justify;\">最早的ALOHA，目前已经不再使用</li><li style=\"text-align: justify;\">帧长一定 =&gt; 帧传输时间一定</li><li style=\"text-align: justify;\">当一帧首次到达（从网络层传下来），结点立即将该帧完整传输进广播信道</li><li style=\"text-align: justify;\">如果发送碰撞，则该结点</li></ul><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Network_Pure-ALOHA.png\" alt=\"\" data-href=\"\" style=\"width: 725.80px;height: 359.90px;\"></p><p style=\"text-align: justify;\">  假设一帧在$t_0$处开始传输，则在$[t_0-1,t_0+1]$，其他结点如有传输，发生碰撞，则易损时间区长度为$2\\tau$（$tau$为一帧的传输时间）。</p><p style=\"text-align: justify;\">  一个结点发送成功，则需要本结点发送、其他结点在$[t_0-1,t_0]$和$[t_0,t_0+1]$不发送。一个给定结点成功传送的概率为</p><p style=\"text-align: justify;\">则有$N$个结点，任意一个结点成功传送的概率为</p><p style=\"text-align: justify;\">如此，求得纯ALOHA的最大效率为$1/(2e)\\approx 0.18$（改变$p$，使$S$最大化）。</p><h4 style=\"text-align: justify; line-height: 1.5;\">时隙ALOHA（Slotted ALOHA）</h4><ul><li style=\"text-align: justify;\">时间被划分成长度相等的时隙（slot）</li><li style=\"text-align: justify;\">结点只在时隙起点开始传输帧</li><li style=\"text-align: justify;\">如果碰撞，在下一时隙的开始以$p$的概率重传，直至成功。</li></ul><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Network_Slotted-ALOHA.png\" alt=\"\" data-href=\"\" style=\"width: 808.80px;height: 434.74px;\"></p><p style=\"text-align: justify;\">  假设一帧在$t_0$处开始传输，则在本时隙中，其他结点如有传输，发生碰撞，则易损时间区长度为$\\tau$（$\\tau$为一帧的传输时间）。</p><p style=\"text-align: justify;\">  一个给定结点成功传送的概率为</p><p style=\"text-align: justify;\">  如果有$N$个活跃结点，任意一个结点成功传送的概率为</p><p style=\"text-align: justify;\">如此，求得时隙ALOHA的最大效率为$1/e\\approx 0.37$（改变$p$，使$S$最大化）。即在有大量结点有帧要传输时，最多$37%$的时隙做有用的工作，信道传输速率不是$R$ bps，而是$0.37R$ bps。</p><p style=\"text-align: justify;\">  时隙ALOHA的最大效率是纯ALOHA的两倍。</p><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Network_ALOHA-Compare.png\" alt=\"\" data-href=\"\" style=\"width: 735.80px;height: 401.48px;\"></p><h4 style=\"text-align: justify; line-height: 1.5;\">CSMA：载波侦听多路访问</h4><p style=\"text-align: justify;\">  载波侦听多路访问（CSMA，Carrier Sense Multiple Access），一个结点在传输前先侦听信道。</p><ul><li style=\"text-align: justify;\">如果侦听到信道空闲，则传输帧</li><li style=\"text-align: justify;\">如果侦听到信道正忙，则推迟传输。再传输方式分为坚持型和非坚持型：坚持型CSMA（Persisitent CSMA）：一直坚持监听，直到信道空闲时，立即以概率$p$重试（可能导致不稳定）。其中1-坚持型CSMA的$p=1$，即立即重试。非坚持型CSMA（Non-Persisitent CSMA）：不再监听，等待一个随机的时间之后再进行监听。</li><li style=\"text-align: justify;\">CSMA依旧会发生碰撞 只要共享信道，那么碰撞就是不可避免的，即使CSMA有侦听。 比如下图中，B结点在$t_0$时传输帧，但是帧的传输是需要一定时间的，这就导致在$t_1$时，D结点侦听判断信道空闲，传输帧。两信号发生碰撞。 如此，整个帧传输时间被浪费了。可以看出，广播信道的端到端信道传播时延（distance and propagation delay）（信号从一个结点到另一个结点的传播时间）在决定性能上起关键作用。</li></ul><h4 style=\"text-align: justify; line-height: 1.5;\">CSMA/CD：具有碰撞检测的载波侦听多路访问</h4><ul><li style=\"text-align: justify;\">碰撞要在短时间内检测出来（最好在一个争用期内）</li><li style=\"text-align: justify;\">一旦检测到碰撞立即停止传输，以减少信道的浪费</li><li style=\"text-align: justify;\">采样坚持型或非坚持型重传</li><li style=\"text-align: justify;\">碰撞检测</li></ul><p style=\"text-align: justify;\">  如下图，当B结点和D结点检测到碰撞时，立即停止继续发送。</p><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Network_CSMA%3ACD.png\" alt=\"\" data-href=\"\" style=\"width: 727.00px;height: 858.31px;\"></p><p style=\"text-align: justify;\"><strong>争用期</strong>：以太网的端到端往返时间$2\\tau$</p><p style=\"text-align: justify;\">  A结点给B结点发送帧流，最坏情况就是在即将发送到B结点时，发生碰撞，返回碰撞信息，最大用时即为$2\\tau$。</p><p style=\"text-align: justify;\"><strong>最短帧</strong>：最短帧长度为$2\\tau R$（$R$为信道速率）</p><p style=\"text-align: justify;\">  和上述同样的最坏情况中，从A结点发送帧，到碰撞信号返回到A结点花费$2\\tau$的时间，在此期间A结点不能停止帧的发送，所以最短帧的长度为$2\\tau R$。</p><p style=\"text-align: justify;\">  如此可以最大利用网络效率，而且不会产生二义型。如果发送完了这个帧，没有发生碰撞，则发生成功。</p><p style=\"text-align: justify;\"><img src=\"https://raw.githubusercontent.com/GY23333/imgs/master/Network_CSMA%3ACD1.png\" alt=\"\" data-href=\"\" style=\"width: 808.80px;height: 493.96px;\"></p><p style=\"text-align: justify;\"><strong>CSMA/CD 效率</strong></p><p style=\"text-align: justify;\">  CSMA/CD 效率：当有大量的活跃结点，且每个结点有大量的帧要发送时，帧在信道中无碰撞地传输的那部分时间在长期运行时间中所占的份额。</p><p style=\"text-align: justify;\">其中，$t_{prop}$为两结点之间的最大传播时间；</p><p style=\"text-align: justify;\">   $t_{trans}$为传输一个最大长度的帧的时间。</p><p style=\"text-align: justify;\">效率趋近1，则需</p><ul><li style=\"text-align: justify;\">$t_{prop}$ -&gt; 0</li><li style=\"text-align: justify;\">或，$t_{trans}$ -&gt; $\\infty$</li></ul><p style=\"text-align: justify;\">  CSMA/CD 比 ALOHA 简单、便宜、分布式。</p><h3 style=\"text-align: justify; line-height: 1.5;\">轮流协议（Taking-Turns protocol）</h3><h4 style=\"text-align: justify; line-height: 1.5;\">轮询协议（Polling protocol）</h4><ul><li style=\"text-align: justify;\">有一个主结点</li><li style=\"text-align: justify;\">主结点以循环的方式轮询每个结点</li><li style=\"text-align: justify;\">主结点先向一个结点发送报文，告诉能够传输的帧的最多的数量，这个结点传输完帧后，主机点再发给下一个结点报文，循环轮询。</li><li style=\"text-align: justify;\">缺点：主结点需先给结点发送报文，增加开销轮询时延，不及时如果主结点出故障，则整个网络无法工作</li></ul><h4 style=\"text-align: justify; line-height: 1.5;\">令牌传递协议（Token-Passing protocol）</h4><ul><li style=\"text-align: justify;\">令牌（token）在结点之间以某种固定次序进行交换</li><li style=\"text-align: justify;\">结点只有在拿到令牌时，才能发送帧</li><li style=\"text-align: justify;\">受控的，不会发生碰撞</li><li style=\"text-align: justify;\">缺点：令牌开销时延令牌环会故障</li></ul>', '', 2, 0, '2024-07-17 14:16:41.541', '2024-07-17 14:24:20.272');
INSERT INTO `articles` (`id`, `user_id`, `category_id`, `title`, `content`, `head_image`, `read_cnt`, `status`, `created_at`, `updated_at`) VALUES (16, 4, 1, 'MySQL 先排序后分组', '<p style=\"text-align: start;\">在<a href=\"https://cloud.tencent.com/product/cdb?from_column=20065&amp;from=20065\" target=\"_blank\">MySQL数据库</a>的数据探索旅程中，排序和分组是不可或缺的工具。然而，当你面对大量数据、重复值等情况时，常规的处理方法可能显得不够灵活。本文将为你揭示一个精妙的技巧：如何在<a href=\"https://cloud.tencent.com/product/cdb?from_column=20065&amp;from=20065\" target=\"_blank\">MySQL</a>中先排序，后分组，从而获取每个类型的最新数据，助你轻松驾驭复杂的数据处理任务。</p><p style=\"text-align: start;\"><br></p><h4 style=\"text-align: start;\"><strong>问题背景：先排序，后分组</strong></h4><p style=\"text-align: start;\">拥有一张包含活动信息的数据表，其中涵盖活动名称、开始时间、类型等字段。你的任务是，根据开始时间先排序，然后在每个类型中选择最新的那条记录，以获取所有信息。</p><h4 style=\"text-align: start;\"><strong>方法一：子查询（5.7版本）</strong></h4><p style=\"text-align: start;\">在子查询中首先对数据进行排序，然后在外部查询中使用分组操作。这样可以保留排序后的顺序，并在分组后选择特定行。</p><p style=\"text-align: start;\">代码语言：javascript</p><p style=\"text-align: start;\"><br></p><pre style=\"text-align: left; line-height: 1.5;\"><code class=\"language-javascript\" style=\"text-align: left; line-height: 1.5;\">select * from (select * from jsontest order by start_time limit 100000 ) T1 group by type order by type \n</code></pre><p style=\"text-align: start;\">这个查询首先将整个表按照开始时间降序排序，然后在外部查询中按类型进行分组，由于已经排序，每个类型中的第一行即为最新的记录。</p><p style=\"text-align: start;\"><strong>注意：此处子查询需要添加limit，limit的值可以根据实际情况调整</strong></p><p style=\"text-align: start;\">在5.7版本中会忽略掉子查询中的order by语句，也就是排序被优化掉了，可以通过在子查询中添加limit来显式的限制生成的子查询结果集</p><h4 style=\"text-align: start;\"><strong>方法二：使用窗口函数（8.0版本）</strong></h4><p style=\"text-align: start;\">通过使用窗口函数（如 ROW_NUMBER()）在内部查询中为每一行分配一个行号，然后在外部查询中筛选行号为1的记录。这样也可以实现先排序后分组的效果。</p><p style=\"text-align: start;\">代码语言：javascript</p><p style=\"text-align: start;\"><br></p><pre style=\"text-align: left; line-height: 1.5;\"><code class=\"language-javascript\" style=\"text-align: left; line-height: 1.5;\">SELECT T1.*\nFROM (\n    SELECT *, ROW_NUMBER() OVER(PARTITION BY type ORDER BY start_time desc) AS rn\n    FROM jsontest\n) T1\nWHERE T1.rn = 1;\n</code></pre><p style=\"text-align: start;\">这个查询在内部查询中使用窗口函数，为每个类型的记录按开始时间降序分配行号，然后在外部查询中选择行号为1的记录，即每个类型的最新记录。</p><h4 style=\"text-align: start;\"><strong>总结</strong></h4><p style=\"text-align: start;\">通过这个先排序，后分组的MySQL魔法，你可以轻松地应对需要复杂数据处理的情况。不再为排序和分组的顺序问题而烦恼，让你的<span style=\"color: rgb(0, 82, 217);\">数据分析</span>更加高效准确。在实际的数据处理中，根据具体的场景选择适合的方法，将会使你在MySQL的世界里游刃有余。</p><p><br></p>', '', 1, 0, '2024-07-17 14:22:03.877', '2024-07-17 14:22:05.235');
INSERT INTO `articles` (`id`, `user_id`, `category_id`, `title`, `content`, `head_image`, `read_cnt`, `status`, `created_at`, `updated_at`) VALUES (17, 1, 4, '进程管理', '<h2 style=\"text-align: left;\">进程的概念和特征</h2><ul><li style=\"text-align: left;\">进程的概念：在多道程序环境下，允许多个程序并发执行，此时它们将失去封闭性，并具有间断性及不可再现性的特征。为此引入了进程（Process）的概念，以便更好地描述和控制程序的并发执行，实现操作系统的并发性和共享性（最基本的两个特性）。为了使参与并发执行的程序（含数据）能独立地运行，必须为之配置一个专门的数据结构，称为进程控制块（Process Control Block，PCB）。系统利用 PCB 来描述进程的基本情况和运行状态，进而控制和管理进程。相应地，由程序段、相关数据段和 PCB 三部分构成了进程映像（进程实体）。所谓创建进程，实质上是创建进程映像中的 PCB；而撤销进程，实质上是撤销进程的 PCB。值得注意的是，进程映像是静态的，进程则是动态的。注意：PCB 是进程存在的唯一标志。</li><li style=\"text-align: left;\">进程的典型定义：进程是程序的一次执行过程。进程是一个程序及其数据在处理机上顺序执行时所发生的活动。进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位（基本单位）。进程是由多道程序的并发执行而引出的，它和程序是两个截然不同的概念。</li><li style=\"text-align: left;\">进程的特征（理解）：进程的基本特征是对比单个程序的顺序执行提出的，也是对进程管理提出的基本要求。动态性：​ 进程是程序的一次执行，它有着创建、活动、暂停、终止等过程，具有一定的生命周期，是动态地产生、变化和消亡的。动态性是进程最基本的特征。并发性：​ 指多个进程实体同时存于内存中，能在一段时间内同时运行。并发性是进程的重要特征，同时也是操作系统的重要特征。引入进程的目的就是使程序能与其他进程的程序并发执行，以提高资源利用率。独立性：​ 指进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。凡未建立 PCB 的程序，都不能作为一个独立的单位参与运行。异步性：​ 由于进程的相互制约，使得进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进。异步性会导致执行结果的不可再现性，为此在操作系统中必须配置相应的进程同步机制。结构性：​ 每个进程都配置一个进程控制块 PCB 对其进行描述。从结构上看，进程实体（也可以说是进程）是由程序段、数据段和 PCB 三部分组成的。</li><li style=\"text-align: left;\">进程和程序的区别：本质区别：进程是动态的；程序是静态的。进程是程序及其数据在计算机上的一次运行活动，是一个动态的概念。定义不同：​ 进程是程序处理数据的过程；程序是一组指令的有序集合。进程的运行实体是程序，离开程序的进程没有存在的意义。组成不同：​ 从静态角度看，进程是由程序、数据和进程控制块（PCB）三部分组成的；程序则是一组代码的集合。生命周期不同：​ 进程是动态地创建和消亡的，具有一定的生命周期，是暂时存在的；程序则是一组代码的集合，是永久存在的，可长期保存。对应关系不同：​ 一个进程可以执行一个或几个程序，一个程序也可构成多个进程。进程可创建进程，而程序不可能形成新的程序。以下三点来自 CSAPP</li><li style=\"text-align: left;\">逻辑控制流：即使在系统中通常有许多其他程序在运行，进程也可以向每个程序提供一种假象，好像它在独占地使用处理器。用调试器单步执行程序，会得到一系列的程序计数器（PC）的值，这些值唯一地对应于包含在程序的可执行目标文件中的指令，或是包含在运行时动态链接到程序的共享对象中的指令。这个 PC 值的序列叫做逻辑控制流，或者简称逻辑流。考虑一个运行着三个进程的系统，如图所示。处理器的一个物理控制流被分成了三个逻辑流，每个进程一个。每个竖直的条表示一个进程的逻辑流的一部分。在这个例子中，三个逻辑流的的关系是：A 和 B 是并发执行的，A 和 C 也是并发执行的（如果两个逻辑流在宏观时间上有重叠，则称这两个进程是并发的）。B 和 C 是顺序执行的。</li><li style=\"text-align: left;\">私有地址空间：进程也为每个程序提供一种假象，好像它独占地使用系统地址空间。进程为每个程序提供它自己的私有地址空间。一般而言，和这个空间中某个地址相关联的那个内存字节是不能被其他进程读或者写的，从这个意义上说，这个地址空间是私有的。尽管和每个私有地址空间相关联的内存的内容一般是不同的，但是每个这样的空间都有相同的通用结构。</li><li style=\"text-align: left;\">上下文切换：操作系统内核使用一种称为上下文切换的较高层形式的异常控制流来实现多任务内核为每个进程维持一个上下文（context），上下文就是内核重新启动一个被抢占的进程所需的状态。它由一些对象的值组成，这些对象包括通用目的寄存器、浮点寄存器、程序计数器、用户栈、状态寄存器、内核栈和各种内核数据结构，比如描述地址空间的页表、包含有关当前进程信息的进程表，以及包含进程已打开文件的信息的文件表。在进程执行的某些时刻，内核可以决定抢占当前进程，并重启一个先前被抢占了的进程。这种决策就叫做调度，是由内核中称为调度器的代码处理的。在内核调度了一个新的进程运行后，它就抢占当前进程，并使用一种称为上下文切换的机制来将控制转移到新的进程：保存当前进程的上下文。恢复某个先前被抢占的进程被保存的上下文。将控制传递给这个新恢复的进程。当内核代表用户执行系统调用时，可能会发生上下文切换。如果系统调用因为等待某个事件发生而阻塞，那么内核可以让当前进程休眠，切换到另一个进程。</li></ul><h2 style=\"text-align: left;\">进程的状态与转换</h2><ul><li style=\"text-align: left;\">状态描述：​ 进程在其生命周期内，由于系统中各进程之间的相互制约关系及系统的运行环境的变化，使得进程的状态也在不断地发生变化（一个进程会经历若干不同状态）。通常进程有以下 5 种状态，前 3 种是进程的基本状态。运行态：​ 进程正在处理机上运行。在单处理机环境下，每个时刻最多只有一个进程处于运行态。就绪态：​ 进程获得了除处理机外的一切所需资源，一旦得到处理机，便可立即运行。系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。不可能所有进程都处于就绪态阻塞态（等待态）：​ 进程正在等待某一事件而暂停运行，如等待某资源为可用（不包括处理机）或等待输入/输出完成。即使处理机空闲，该进程也不能运行。创建态：​ 进程正在被创建，尚未转到就绪态。创建进程通常需要多个步骤：申请一个空白的 PCB，并向 PCB 中填写一些控制和管理进程的信息由系统为该进程分配运行时所必需的资源把该进程转入就绪态结束态：​ 进程正从系统中消失，可能是进程正常结束或其他原因中断退出运行。进程需要结束运行时，系统首先必须将该进程置为结束态，然后进一步处理资源释放和回收等工作。</li><li style=\"text-align: left;\">状态转换：就绪态 → 运行态：​ 处于就绪态的进程被调度后，获得处理机资源（分派处理机时间片），于是进程由就绪态转换为运行态。运行态 → 就绪态：处于运行态的进程在时间片用完后，不得不让出处理机，从而进程由运行态转换为就绪态。在可抢占的操作系统中，当有更高优先级的进程就绪时，程序将正在执行的进程转换为就绪态，让更高优先级的进程执行。运行态 → 阻塞态：​ 进程请求某一资源（如外设）的使用和分配或等待某一事件的发生（如 I/O 操作的完成）时，它就从运行态转换为阻塞态。阻塞态 → 就绪态：​ 进程等待的事件到来时，如 I/O 操作结束或中断结束时，中断处理程序必须把相应进程的状态由阻塞态转换为就绪态。</li></ul><h2 style=\"text-align: left;\">进程控制</h2><ul><li style=\"text-align: left;\">进程的创建：允许一个进程创建另一个进程。此时创建者称为父进程，被创建的进程称为子进程。子进程可以继承父进程所拥有的资源。当子进程被撤销时，应将其从父进程那里获得的资源归还给父进程。在撤销父进程时，必须同时撤销其所有的子进程。操作系统创建一个新进程的过程如下（创建原语）：为新进程分配一个唯一的进程标识号，并申请一个空白的 PCB（PCB 是有限的）。若 PCB 申请失败，则创建失败。为进程分配资源，为新进程的程序和数据及用户栈分配必要的内存空间（在 PCB 中体现）。若资源不足（如内存空间），则并不是创建失败，而是处于阻塞态，等待内存资源。初始化 PCB，主要包括初始化标志信息、处理机状态与控制信息，以及设置进程的优先级等。若进程就绪队列能够接纳新进程，则将新进程插入就绪队列，等待被调度运行。</li><li style=\"text-align: left;\">进程的终止:引起进程终止的事件主要有：正常结束：​ 表示进程的任务已完成并准备退出运行。异常结束：​ 表示进程在运行时，发生了某种异常事件，使程序无法继续运行，如存储区越界、保护错、非法指令、特权指令错、运行超时、算术运算错、I/O 故障等。外界干预：​ 指进程应外界的请求而终止运行，如操作员或操作系统干预、父进程请求和父进程终止。操作系统终止进程的过程如下（撤销原语）：根据被终止进程的标识符，检索 PCB，从中读出该进程的状态。若被终止进程处于执行状态，立即终止该进程的执行，将处理机资源分配给其他进程。若该进程还有子孙进程，则应将其所有子孙进程终止。将该进程所拥有的全部资源，或归还给其父进程，或归还给操作系统。将该 PCB 从所在队列（链表）中删除。</li><li style=\"text-align: left;\">进程的阻塞和唤醒：正在执行的进程，由于期待的某些事件未发生，如请求系统资源失败、等待某种操作的完成、新数据尚未到达或无新工作可做等，由系统自动执行阻塞原语（Block），使自己由运行态变为阻塞态。进程的阻塞是进程自身的一种主动行为，也因此只有处于运行态的进程（获得 CPU），才可能将其转为阻塞态。阻塞原语的执行过程如下：找到将要被阻塞进程的标识号对应的 PCB。若该进程为运行态，则保护其现场，将其状态转为阻塞态，停止运行。把该 PCB 插入相应事件的等待队列，将处理机资源调度给其他就绪进程。当被阻塞进程所期待的事件出现时，如它所启动的 I/O 操作已完成或其所期待的数据已到达，由有关进程（比如，释放该 I/O 设备的进程，或提供数据的进程）调用唤醒原语（Wakeup），将等待该事件的进程唤醒。唤醒原语的执行过程如下：在该事件的等待队列中找到相应进程的 PCB.将其从等待队列中移出，并置其状态为就绪态。把该 PCB 插入就绪队列，等待调度程序调度。需要注意的是，Block 原语和 Wakeup 原语是一对作用刚好相反的原语，必须成对使用。Block 原语是由被阻塞进程自我调用实现的，而 Wakeup 原语则是由一个与被唤醒进程合作或被其他相关的进程调用实现的。</li><li style=\"text-align: left;\">进程切换：对于通常的进程而言，其创建、撤销及要求由系统设备完成的 I/O 操作，都是利用系统调用而进入内核，再由内核中的相应处理程序予以完成的。进程切换同样是在内核的支持下实现的，因此可以说，任何进程都是在操作系统内核的支持下运行的，是与内核紧密相关的。进程切换是指处理机从一个进程的运行转到另一个进程上运行，在这个过程中，进程的运行环境产生了实质性的变化。进程切换的过程如下：保存处理机上下文，包括程序计数器和其他寄存器。更新 PCB 信息。把进程的 PCB 移入相应的队列，如就绪、在某事件阻塞等队列。选择另一个进程执行，并更新其 PCB.更新内存管理的数据结构（可能要刷新 TLB 之类的）。恢复处理机上下文。</li></ul><h2 style=\"text-align: left;\">进程 Unix 代码</h2><ul><li style=\"text-align: left;\">获取进程 ID：​ 每个进程都有一个唯一的正数（非零）进程 ID（PID）。</li></ul><pre><code class=\"language-cpp\">pid_t getpid(void);  /* 返回调用进程的PID */\r\npid_t getppid(void); /* 返回调用进程的父进程的 PID */</code></pre><ul><li style=\"text-align: left;\">exit 终止进程</li></ul><pre><code class=\"language-cpp\">/* exit 函数以 status 退出状态来终止进程。正常结束时返回 0 , 错误时返回非 0 值*/\r\nvoid exit(int status);</code></pre><ul><li style=\"text-align: left;\">fork() 创建进程：子进程得到与父进程用户级虚拟地址空间相同的（但是独立的）一份副本，包括代码和数据段、堆、共享库以及用户栈。子进程还获得与父进程任何打开文件描述符相同的副本，这就意味着当父进程调用 fork() 时，子进程可以读写父进程中打开的任何文件。父进程和新创建的子进程之间最大的区别在于它们有不同的 PID。fork() 函数只被调用一次，却会返回两次。一次是在调用进程（父进程）中，一次是在新创建的子进程中：在父进程中，fork() 返回子进程的 PID。在子进程中，fork() 返回 0。因为子进程的 PID 总是为非零，返回值就提供一个明确的方法来分辨程序是在父进程还是在子进程中执行。</li><li style=\"text-align: left;\">进程回收：当一个进程由于某种原因终止时，内核并不是立即把它从系统中清除，而是被保持在一种已终止的状态中，直到被它的父进程回收。当父进程回收已终止的子进程时，内核将子进程的退出状态传递给父进程，然后抛弃已终止的进程，从此时开始，该进程就不存在了。一个终止了但还未被回收的进程称为僵死进程。如果一个父进程终止了，内核会安排 init 进程成为它的孤儿进程的养父。init 进程的 PID 为 1，是在系统启动时由内核创建的，它不会终止，是所有进程的祖先。如果父进程没有回收它的僵死子进程就终止了，那么内核会安排 init 进程去回收它们。即使僵死子进程没有运行，它们仍然消耗系统的内存资源。一个进程可以通过调用 waitpid 函数来等待它的子进程终止或者停止。</li></ul><p style=\"text-align: left;\"><img src=\"http://120.46.13.13:8080/images/image_20240717142206.png\" alt=\"\" data-href=\"\" style=\"\"></p>', '', 1, 0, '2024-07-17 14:22:30.733', '2024-07-17 14:25:51.989');
INSERT INTO `articles` (`id`, `user_id`, `category_id`, `title`, `content`, `head_image`, `read_cnt`, `status`, `created_at`, `updated_at`) VALUES (18, 1, 1, '关系代数的基本运算', '<p><br></p><h2>5 种基本的关系代数运算</h2><h3>并（Union）</h3><p>关系 R 与 S 具有相同的关系模式，即 R 与 S 的元数相同（结构相同），R 与 S 的并是属于 R <strong>或</strong> 属于 S 的元组构成的集合，记作 R ∪ S，定义如下：</p><p>𝑅∪𝑆={𝑡|𝑡∈𝑅∨𝑡∈𝑆}</p><h3>差（Difference）</h3><p>关系 R 与 S 具有相同的关系模式，关系 R 与 S 的差是属于 R <strong>且</strong> 不属于 S 的元组构成的集合，记作 R − S，定义如下：</p><p>𝑅−𝑆={𝑡|𝑡∈𝑅∧𝑡∉𝑆}</p><h3>广义笛卡尔积（Extended Cartesian Product）</h3><p>两个无数分别为 n 目和 m 目的关系 R 和 S 的 笛卡尔积是一个 (n+m) 列的元组的集合。组的前 n 列是关系 R 的一个元组，后 m 列是关系 S 的一个元组，记作 R × S，定义如下：</p><p>𝑅×𝑆=𝑡|𝑡=&lt;(𝑡𝑛,𝑡𝑚)∧𝑡𝑛∈𝑅∧𝑡𝑚∈𝑆</p><p> 表示元素 &nbsp;和 &nbsp;拼接成的一个元组</p><h3>投影（Projection）</h3><p>投影运算是从关系的垂直方向进行运算，在关系 R 中选出若干属性列 A 组成新的关系，记作 ，其形式如下：</p><p>𝜋𝐴(𝑅)={𝑡[𝐴]|𝑡∈𝑅}</p><h3>选择（Selection）</h3><p>选择运算是从关系的水平方向进行运算，是从关系 R 中选择满足给定条件的元组，记作 ，其形式如下：</p><p>𝜎𝐹(𝑅)=𝑡|𝑡∈𝑅∧𝐹(𝑡)=𝑇𝑟𝑢𝑒</p><h2>实例</h2><p>设有关系 R、S 如图所示，求 、 、 、 、 &nbsp;和 </p><p><img src=\"https://img10.360buyimg.com/devfe/jfs/t3967/269/2409299226/5377/e997b909/58a95fceNddd39fd7.png\" alt=\"关系表RS\" data-href=\"\" style=\"height: auto;\"/></p><p>进行并、差运算后结果如下：</p><p><img src=\"https://img14.360buyimg.com/devfe/jfs/t3949/95/2458170516/5487/1c7f1f38/58a967b1N42db123f.png\" alt=\"并差\" data-href=\"\" style=\"height: auto;\"/></p><p>进行笛卡尔、 投影、 选择运算后结果如下：</p><p><img src=\"https://img30.360buyimg.com/devfe/jfs/t3943/109/2403665652/38834/c636281b/58a9685dN20af0b9b.png\" alt=\"笛卡尔_投影_选择\" data-href=\"\" style=\"height: auto;\"/></p><h2>扩展的关系代数运算</h2><h3>交（Intersection）</h3><p>关系 R 和 S 具有相同的关系模式，交是由属于 R 同时双属于 S 的元组构成的集合，记作 R∩S，形式如下：</p><p>𝑅∩𝑆=𝑡|𝑡∈𝑅∧𝑡∈𝑆</p><h3>链接（Join）</h3><p>注：下面的 θ 链接应该记作：<img src=\"https://img10.360buyimg.com/devfe/jfs/t3967/158/2461240249/2389/530d7d07/58aa580aNe9908740.png\" alt=\"theta链接\" data-href=\"\" style=\"height: auto;\"/></p><h4>θ 链接</h4><p>从 R 与 S的笛卡尔积中选取属性间满足一定条件的元组，可由基本的关系运算笛卡尔积和选取运算导出，表示为：</p><p>𝑅⋈𝑋𝜃𝑌𝑆=𝜎𝑋𝜃𝑌(𝑅×𝑆)</p><p>XθY 为链接的条件，θ 是比较运算符，X 和 Y 分别为 R 和 S 上度数相等且可比的属性组</p><p>例如：求 ，如果为：</p><p><img src=\"https://img14.360buyimg.com/devfe/jfs/t3133/127/6662942086/21071/88c200da/58aa5b1fN3e2316d5.png\" alt=\"theta链接小于过程\" data-href=\"\" style=\"height: auto;\"/></p><h4>等值链接</h4><p>当 θ 为「=」时，称之为等值链接，记为： </p><h4>自然链接</h4><p>自然链接是一种特殊的等值链接，它要求两个关系中进行比较的分量必须是 <strong>相同的属性组</strong>，并且在结果集中将 <strong>重复的属性列</strong> 去掉</p><p>例如：设有关系 R、S 如图所示，求 </p><p><img src=\"https://img11.360buyimg.com/devfe/jfs/t3982/212/2472511181/5973/54467e2a/58aa5ffaN970f7e5a.png\" alt=\"关系RS\" data-href=\"\" style=\"height: auto;\"/></p><p>先求出笛卡尔积 ，找出比较分量（有相同属性组），即: R.A/S.A 与 R.C/S.C</p><p><img src=\"https://img10.360buyimg.com/devfe/jfs/t3841/5/4275908218/12385/79e83d01/58aa6066Nd003e697.png\" alt=\"求出笛卡尔积\" data-href=\"\" style=\"height: auto;\"/></p><p>取等值链接 &nbsp;且 </p><p><img src=\"https://img10.360buyimg.com/devfe/jfs/t3256/75/6205568741/12327/2b1dc867/58aa60e8N38a84108.png\" alt=\"找出相同属性的比较分量\" data-href=\"\" style=\"height: auto;\"/></p><p>结果集中去掉重复属性列，注意无论去掉 R.A 或者 S.A 效果都一样，因为他们的值相等，结果集中只会有属性 A、B、C、D</p><p><img src=\"https://img12.360buyimg.com/devfe/jfs/t3217/183/6576493853/4744/ccb96965/58aa612eN043f7425.png\" alt=\"结果集中找出重复属性列\" data-href=\"\" style=\"height: auto;\"/></p><p>最终得出结果</p><p><img src=\"https://img12.360buyimg.com/devfe/jfs/t3247/65/6676502314/2874/657ddb0c/58aa617eN2457f536.png\" alt=\"RS自然链接结果\" data-href=\"\" style=\"height: auto;\"/></p><h3>除（Division）</h3><p>设有以下如图关系，求 </p><p><img src=\"https://img10.360buyimg.com/devfe/jfs/t3151/348/6716540896/7287/dc01ad2e/58aaaf3bN1cae8b1a.png\" alt=\"关系RS1\" data-href=\"\" style=\"height: auto;\"/></p><p>取关系 R 中有的但 S 中没有的属性组，即：A、B</p><p><img src=\"https://img11.360buyimg.com/devfe/jfs/t3202/137/6722879648/7244/3b47a185/58aaaf81N0b2491b5.png\" alt=\"关系RS1取属性AB\" data-href=\"\" style=\"height: auto;\"/></p><p>取唯一 A、B 属性组值的象集</p><p><img src=\"https://img11.360buyimg.com/devfe/jfs/t3871/170/2430481542/5179/be5899c5/58aaafe6N8297b49f.png\" alt=\"关系RS1取属性AB对应的象集\" data-href=\"\" style=\"height: auto;\"/></p><p>可知关系S存在于 a,b/c,k 象集 中。即 &nbsp;得</p><p><img src=\"https://img10.360buyimg.com/devfe/jfs/t3130/361/6704334588/3366/6b7e0b56/58aab058N3a3c374d.png\" alt=\"关系RS1除结果\" data-href=\"\" style=\"height: auto;\"/><br></p>', '/images/image_20240717142517.png', 3, 0, '2024-07-17 14:25:24.299', '2024-07-17 15:06:29.495');
INSERT INTO `articles` (`id`, `user_id`, `category_id`, `title`, `content`, `head_image`, `read_cnt`, `status`, `created_at`, `updated_at`) VALUES (19, 4, 4, '计算机及操作系统原理', '<p style=\"text-align: left;\">一、操作系统的概念</p><p style=\"text-align: left;\">定义：从本质上来说操作系统就是把底层硬件抽象成了一层虚拟机，所以说计算机本身就是一个虚拟机。计算机本身并不会做任何事情，它就是一堆铁疙瘩，即使给它加电它也不会做任何事情，cpu只有在程序的指挥下才会做事情。所以，操作系统的启动就是一个自举的过程，上电的一刹那间主板上的一块ROM芯片中的代码会被自动映射到内存的低地址空间，这块ROM芯片中存的就是BIOS。　　</p><p style=\"text-align: left;\">二、核心五大部件</p><p style=\"text-align: left;\">在冯诺依曼体系中，计算机有五大部件，分别是运算器、控制器、寄存器、输入设备和输出设备。其中CPU最核心的是运算器、控制器和寄存器。</p><p style=\"text-align: left;\"><strong>运算器</strong>：负责算术、逻辑运算等，</p><p style=\"text-align: left;\"><strong>控制器</strong>：控制指令，包括数据的存取过程。程序就是由指令+数据组成的</p><p style=\"text-align: left;\"><strong>寄存器</strong>（Register）：将取回的数据暂存于此，同时起到中间数据计算结果存放的功能。</p><p style=\"text-align: left;\">因此运算器在控制器的控制下不断从寄存器中读取数据处理，在计算机内部的存储器速度是最快的，称为寄存器（暂存）。之所以称为寄存器是因为里面的数据刷新频率很快可以跟CPU刷新频率同步，接下来比较快的是一级缓存、二级缓存、三级缓存，再到外面就是内存了，从内到外造价越来越低，存取速度越来越慢，容量越来越大。一级缓存又被分为一级指令缓存，一级数据缓存；二级缓存就没有这样区分了。多核CPU，每一核CPU都有自己一级、二级缓存，而三级缓存是共享的。</p><p style=\"text-align: left;\">寄存器固然能存储数据，但是空间太小，不是存储设备的核心部件，因此必须要跟内存设备打交道</p><p style=\"text-align: left;\"><strong>内存（RAM）</strong>：由多个存储单元组成，一个字节为一个存储单元，或者一个cell为一个存储单元。每个cell都有自己的存储地址，以16进制进行编制。</p><p style=\"text-align: left;\">CPU要想存取数据，就需要知道内存中数据的存储地址，必须要具备寻址数据功能。</p><p style=\"text-align: left;\"><strong>北桥芯片（NorthBridge）</strong>：用来处理高速信号。通常处理CPU（处理器）、RAM（内存）、AGP端口或PCI Express和南桥芯片之间的通信。即是CPU电路单元和RAM的存储电路建立关联关系</p><p style=\"text-align: left;\"><strong>32位CPU</strong>：相当于CPU有32根地址线与内存相连，每根地址线都能传输0和1两个位的信号，即能处理的信息为2^32bits=512Mbyte，32根线总共会决定出2^32次方个位置，每一个位置都是1Byte,这是内存的基本单位，因此最多能支持的内存为2^32Byte=4GB。同理64位CPU，4G*4G相当于40多亿个4G。</p><p style=\"text-align: left;\"> <img src=\"http://120.46.13.13:8080/images/image_20240717143144.png\" alt=\"\" data-href=\"\" style=\"width: 506.00px;height: 391.64px;\"></p><p style=\"text-align: left;\"> </p><p style=\"text-align: left;\">CPU完成寻址的线路、数据读取的线路、控制指令线路，如果每个线路都配上32根地址线就变得相当复杂，因此CPU将这些线路进行复用（<strong>线路复用</strong>），通过控制位来区分哪些是数据读取、哪些上寻址等</p><p style=\"text-align: left;\"><strong>PAE（物理地址扩展）</strong>：Physical Address Extension。在32位（bit）寻址总线的基础上再增加4bit相当于2^36Byte=64G，但是需要操作系统内核支持寻址64G的能力。32位操作系统无论内核是否支持PAE，单个进程的所能使用的地址空间超不过3G，剩下1G映射给内核了。例如MySQL就是单进程多线程运行，在32位操作系统上最多能使用的内存只有2.7G，因此最好使用64位的操作系统安装64位的MySQL。</p><p style=\"text-align: left;\">这里牵扯到一个问题，为什么缓存可以提高速度？是因为程序的局部性原理，就是我们常说的二八法则。一段程序中执行频率最高的代码往往只有20%，80%的代码很少用到，而这20％的代码完成了整个程序80%的功能。我们可以将这20%的代码缓存到cpu一级缓存或者二级缓存中，因为cpu中的cache的速度和cpu的时钟频率最接近，这样就可以提高程序运行的速度，</p><p style=\"text-align: left;\">一般缓存算法设计的思路都是：最近最少使用原则。将最近最少使用的数据从缓存中移除，毕竟缓存的空间是有限的，要是缓存和内存的价格一样，那就没必要设计缓存了。程序的局部性原理分为空间局部性和时间局部性：空间局部性是指一段代码被访问了，那么它周围的代码也极有可能被访问到。时间局部性是指某一时刻一段代码被访问了，那么过一会儿这段代码极有可能被再次访问。</p><p style=\"text-align: left;\"><strong>N路关联：</strong>PC机一级缓存空间通常为64KB，而内存远远大于一级缓存。但是CPU读取数据一定是来自一级缓存的，一级缓存没有就去二级缓存寻找，找到即替换一级缓存中的，反之一层一层往下找，直到内存中。由于一级缓存与内存差异巨大，CPU命中需要数据的概率极低。RAM中的每个存储单元都可以直接缓存在一级缓存中的每一个位置，这叫<strong>直接映射</strong>，因此为了提高命中率引入了N路关联技术。原理上将RAM分为几片，同理一级缓存也分为对应的几片，如下图，所谓1路关联（1 way），内存中的00、08、16、24只能缓存在set 0单元上，01、09、17、25只能缓存在set1单元上，如果00已经在set0单元上，此时08想缓存在set0上，就要将00置换掉</p><p style=\"text-align: left;\"><img src=\"http://120.46.13.13:8080/images/image_20240717143211.png\" alt=\"\" data-href=\"\" style=\"\"></p><p style=\"text-align: left;\"><strong>2路关联</strong></p><p style=\"text-align: left;\">如下图，00、08可以同时缓存在set0单元上，而16、24想缓存时需要置换前两个</p><p style=\"text-align: left;\"> <img src=\"http://120.46.13.13:8080/images/image_20240717143221.png\" alt=\"\" data-href=\"\" style=\"\"></p><p style=\"text-align: left;\"><strong>4路关联</strong></p><p style=\"text-align: left;\">如下图，00、08、16、24可以同时缓存在set0单元上，而01、09、17、25想缓存时需要置换前四个</p><p style=\"text-align: left;\"><strong> </strong><img src=\"http://120.46.13.13:8080/images/image_20240717143227.png\" alt=\"\" data-href=\"\" style=\"\"></p><p style=\"text-align: left;\"><strong>完全关联</strong></p><p style=\"text-align: left;\"> <img src=\"http://120.46.13.13:8080/images/image_20240717143237.png\" alt=\"\" data-href=\"\" style=\"\"></p><p style=\"text-align: left;\"><strong>通写策略（write-through）</strong>：在数据更新时，同时写入缓存Cache和后端存储。此模式的优点是操作简单；缺点是因为数据修改需要同时写入存储，数据写入速度较慢。</p><p style=\"text-align: left;\"><strong>回写策略（Write-back）：</strong>在数据更新时只写入缓存Cache。只在数据被替换出缓存时，被修改的缓存数据才会被写到后端存储。此模式的优点是数据写入速度快，因为不需要写存储；缺点是一旦更新后的数据未被写入存储时出现系统掉电的情况，数据将无法找回。</p><p style=\"text-align: left;\"><strong>显卡（video card）</strong>：跟CPU数据交互量上非常大的，也是接在北桥上的，是一个高速总线。</p><p style=\"text-align: left;\"><strong>IO设备</strong>：除了CPU中的运算器、控制器、寄存器之外的设备都是IO设备，IO设备分为低速IO和高速IO。高速IO通常指的的PCI总线</p><p style=\"text-align: left;\">为了衔接计算机系统中各个速度比cpu慢的设备，早期的主板上集成有北桥芯片和南桥芯片（现在的主板可能已经不是这么设计了），南桥芯片是将各慢速设备汇总起来一起接入北桥芯片，所以桥接芯片说白了就是汇总各外部设备最终完成和cpu的交互。south bridge上接的通常称为ISA总线，早期的PCI总线都是接到南桥上的，接入北桥的称为PCI-E，PCI-E总线的速度比PCI总线的速度要快得多得多。常见的磁盘总线都是PCI格式的，SCSI、IDE、SATA统称为PCI总线，PCI（外部设备互连）只是一种统称。鼠标、键盘是串行接口的，通常U盘是通过PCI总线连接南桥-北桥-CPU进行数据交互的。如果把U盘做成PCI-E接口，线路带宽足够大，而U盘太慢了，此时把N个U盘并行连接当作一个存储盘使用，由一根PCI-E总线连接北桥与CPU进行数据交互，这种称为固态硬盘。现在很多固态硬盘接口都上SATA接口，建议购买PCI-E接口的固态硬盘。那么问题来了，计算机接了这么多的外部设备，cpu如何区分不同的IO设备呢？类比计算机区分和互联网通信的各个进程的方法，计算机区分不同的和外部通信的进程靠的是套接字，也就是ip地址+端口号。这里cpu区分不同IO设备靠的也是端口号，称为IO端口，在一台计算机上IO端口的数目也是65535个。任何一个硬件设备通过IO总线接入计算机的时，它必须一开机就申请注册一批连续的IO端口。</p><p style=\"text-align: left;\">任何一个硬件设备的电路可能跟CPU内部电路不一致，因此每一个外部设备都有控制器、适配器，控制器和适配器是将外部设备的信号转换成连接CPU总线上能理解的信号，相当于翻译官，同时控制外部设备的传输速率、校验等功能。所谓驱动就是指挥控制器芯片与硬件工作的。</p><p style=\"text-align: left;\"><strong>轮巡（poll）</strong>：CPU连接这么多外接设备，是如何区分电信号是来自硬盘、鼠标还是网卡，它每隔几毫秒去轮巡一次，查看这些设备有没有信号传输。</p><p style=\"text-align: left;\"><strong>中断（interrupt）</strong>：因poll效率非常低，因此每个设备发送信号时通知CPU来查看，CPU怎么得知是哪个设备的信号呢？可能你会想到通过IO端口来识别，IO端口是实现数据交互而不是识别信号交互的</p><p style=\"text-align: left;\"><strong>中断控制器（Interrupt Controller）</strong>：CPU外置芯片，接收中断信号。当某个外部设备（例如网卡卡）传来信号，CPU中断当前操作，将此信号接收至内存中。中断控制器上连接着中断线，每根线代表一个设备（不是固定的设备），用来区分外部设备，线路是可以复用的，</p><p style=\"text-align: left;\"><strong>直接内存存取（DMA）</strong>：如果CPU需要处理每个外部设备发来的信号，将会使CPU很繁琐，因此引用DMA来解决这个问题。由CPU在内存中划好某次传输数据所需空间，并授权某根线路给DMA使用。它允许不同速度的硬件装置来沟通，而不需要依赖于 CPU 的大量中断负载。否则，CPU 需要从来源把每一片段的资料复制到暂存器，然后把它们再次写回到新的地方。在这个时间中，CPU 对于其他的工作来说就无法使用。</p><p style=\"text-align: left;\">在实现DMA传输时，是由DMA控制器直接掌管总线，因此，存在着一个总线控制权转移问题。即DMA传输前，CPU要把总线控制权交给DMA控制器，而在结束DMA传输后，DMA控制器应立即把总线控制权再交回给CPU。一个完整的DMA传输过程必须经过DMA请求、DMA响应、DMA传输、DMA结束4个步骤。</p><p style=\"text-align: left;\">在物理内存当中，最低地址那段空间，最容易寻址的那段空间的起始地址就预留给DMA，一般16M，在DMA最前面还有1M使用的空间是留给BIOS。</p><p style=\"text-align: left;\">CPU工作频率比较快，内存工作频率比较慢，当内存传输数据给CPU时，CPU大部分时间上处于空闲状态的，因此CPU与慢设备打交道时，会浪费许多时钟周期。CPU内部有一个时间产生器（晶体振荡器），始终产生着时钟脉冲。如下图CPU已经转了好几个周期才开始与内村打交道。CPU为了协调步伐一致，要规划好多少个周期后与内存交互。一般上在时钟周期的上升沿（即高电平与低电平进行切换时）进行交互。</p><p style=\"text-align: left;\"><strong>操作系统</strong>：CPU与外部设备交互经常步伐不一致，为了合理利用CPU资源，即衍生出了Monitor（监控器），发展到后来就成为OS（操作系统），再后来操作系统把计算机抽象成虚拟机。</p><p style=\"text-align: left;\">之所以把操作系统称为虚拟机，是因为我们只有一块cpu芯片(可能是多核心的)，只有一块内存，鼠标只有一个，键盘只有一个........但是每个进程都想独占这一整套资源。cpu通过时间片轮转的方式将一个cpu芯片虚拟成多个cpu进行，内存的虚拟通过分页机制，将内存切割成一个个固定大小的页面。好了，现在已经把计算机系统中最重要的两个部件运算器和存储器虚拟出来了（其实就是虚拟的cpu和内存）,剩下的那些IO设备如何虚拟呢？其实在IO虚拟不需要专门去做，因为当前哪个进程获得了系统使用权，IO设备就交给整个进程。</p><p style=\"text-align: left;\"><strong>进程</strong>：一个程序有许多功能，但加载程序的部分功能到CPU中执行的实例称为进程，相当于一个独立运行单位。</p><p style=\"text-align: left;\">多个独立进程同时运行，CPU、缓存、内存、IO设备上如何合理的分配资源的？</p><p style=\"text-align: left;\">1、 <strong>CPU</strong>：将时间切割成各个独立单位，在时间的维度完成切片进而完成CPU虚拟。</p><p style=\"text-align: left;\">2、 <strong>缓存</strong>：有足够空间可用即不需要做什么，如果没有的话，则要进行保存。但是这个进程还没有执行完，CPU分配的时间已经到下一个进程了，此时就要保存现在这个进程的指令数（CPU内部的指令计数器：寄存器），也就是保存现场，再次回来就要恢复现场</p><p style=\"text-align: left;\">3、 <strong>内存</strong>：将空间切片，内核预留一部分，依次分给进程1、进程2等等以此类推，如果是这样划分的话，进程随时启动，随时终止，或者有的进程需要的空间大，有的小，划分的空间进程不够用，有的划分得太多，所以得引入内存保护机制。如此只能将内存按固定大小进行切割，例如按4k大小为一个单位（存储槽）进行切割，每个存储槽为一个页框（page frame），每个存储槽存储的数据叫一个页面（page），在页面和页框上加一个页和页框的映射机制，这个映射上面的进程都各自认为自己拥有所有内存。进程空间（指令区+代码区+数据区+bss段+堆+栈）如，指令一个页，代码一个页，数据两个页等，如下图，代码区和栈由控制芯片映射到内存中的某个页框上，并不是连续的页框。站在进程的角度来讲，它所需数据的地址是线性地址，而真正数据上存放在物理地址，因此需要通控制芯片进行查找，如此多的数据，控制芯片是如何快速查找的呢？其实在控制芯片里将两者的对应关系划分成了页目录（一级目录、二级目录、三级目录等）</p><p style=\"text-align: left;\"><img src=\"http://120.46.13.13:8080/images/image_20240717143314.png\" alt=\"\" data-href=\"\" style=\"\"></p><p style=\"text-align: left;\"> &nbsp; &nbsp; &nbsp; 4、<strong>I/O设备</strong>：要跟硬件（即I/O设备）打交道必须通过内核，由内核转给进程。</p><p style=\"text-align: left;\">　　cpu芯片只有一块，在某一时刻，要么是内核进程在上面运行，要么是用户空间进程在上面运行，内核在cpu上运行时称为内核模式，进程在cpu上运行时称为用户模式。而在内存中内核占据的那段内存空间称为内核空间，用户进程占据的空间叫用户空间。用户模式时，进程是不能直接控制硬件的。这是因为在cpu内部，cpu制造商将cpu能运行的指令划分为４层(仅对x86架构而言)，ring0，ring1，ring2，ring3，由于历史原因，ring1和ring2并没有使用，linux只用了ring0和ring3。ring0称为内核模式，也称为特权指令模式，可以直接操控硬件，ring3是用户模式，可以执行一般指令。</p><p style=\"text-align: left;\">当一个运行中的进程要打开文件或者操作麦克风，它发现自己没有权限执行特权指令，于是就会发起系统调用，一旦产生系统调用进程就会退出，从用户模式切换到特权模式，称为模式切换。由内核负责将数据装载至物理内存（物理内存为内核与各进程用户都划分了一段自己的空间）先到内核空间中，再转至进程用户空间，然后映射到线性地址上，这个时候内核再唤醒用户进程进行数据交互。如果有多个进程，即进程队列，这里就牵扯到进程的状态了，这里简单介绍几个。就绪状态：就绪是指在所有进程队列中，这个进程所需的所有资源都已经准备好了。没有就绪的称为睡眠状态，而睡眠状态又分为可中断睡眠和不可中断睡眠，区别是：可中断睡眠是指随时可以唤醒的，不可中断睡眠是指内核为它准备的数据还没有准备好，即使唤醒它，它也不能干活。可中断睡眠不是因为资源没有准备好而睡眠，只是一个阶段的活已经干完了，下一阶段的活儿还没来，于是它就去睡觉了，你可以随时叫醒它，所以称可中断睡眠。而不可中断睡眠一般是因为IO而进入睡眠状态的。</p><p style=\"text-align: left;\"><strong>进程结构</strong>：进程是通过双向链表（List）来管理的，而这个链表是有次序的。如下图：通过其中一个可以找到下一个，每个进程在Linux内核内部靠一个独立的数据结构来管理，这个结构叫Task_structure（C语言描述独立数据组织的数据结构），而这个整体文件也被称作进程描述符（类似文件的元数据）。每个进程都有进程描述符，在创建一个进程时，首先创建一个<strong>进程描述符</strong>，并添加到双向链表上，删除则在此表上删除描述符。</p><p style=\"text-align: left;\"> <img src=\"http://120.46.13.13:8080/images/image_20240717143325.png\" alt=\"\" data-href=\"\" style=\"\"></p><p style=\"text-align: left;\"> </p><p style=\"text-align: left;\">从内核观点看，创建一个进程除了要给进程分配系统资源(CPU 时间、内存等)，还要在内核的内存空间中给它维护一个进程描述符文件。这个文件保存着当前进程的所有相关信息，这个文件结构如下：</p><p style=\"text-align: left;\"> <img src=\"http://120.46.13.13:8080/images/image_20240717143334.png\" alt=\"\" data-href=\"\" style=\"\"></p><p style=\"text-align: left;\"><strong>进程切换（Context switch）</strong>：又称为上下文切换。如下图A进程和B进程进行切换。</p><p style=\"text-align: left;\"> <img src=\"http://120.46.13.13:8080/images/image_20240717143347.png\" alt=\"\" data-href=\"\" style=\"\"></p><p style=\"text-align: left;\">假如，B进程替换A进程，A的进程描述符（task_struct）要被CPU挂起（suspend），意味着在CPU上的占位符（stack pointer）、其他寄存器（other registers）、指令计数器（EIP register）等等所维持的数据都需要保存到A进程描述符文件当中（称为保存现场），而进程描述符是由内核维护着，描述符大小是固定的。当A进程被挂起，B进程就被执行进来，这个过程叫恢复现场（resume）。可以看出上下文切换也是需要花时间的，而且上下文切换是由内核来完成，意味着每一次进程切换都要从用户模式转到内核模式，然后再到用户模式如此这样运行下去，不可能一个进程直接到另一个进程，必须由内核完成，则整体时间被分为两部分（用户模式所占据的时间(%us)+内核模式所占据的时间）。所有内核占据的这部分时间就是下图的%sy所占据时间</p><p style=\"text-align: left;\"><img src=\"http://120.46.13.13:8080/images/image_20240717143401.png\" alt=\"\" data-href=\"\" style=\"\"></p><p style=\"text-align: left;\">通常内核模式是不应该占据太多时间的，如果占用时间过多大都是进程切换，中断次数等过多导致的，而进程大部分时间是跟用户模式打交道的。 </p><p style=\"text-align: left;\"><strong>进程抢占</strong>：根据时钟中断抢占，也就是系统时钟（内部时钟频率），称为嘀嗒（tick）。</p><p style=\"text-align: left;\">注：Linux有系统时钟和硬件时钟。</p><p style=\"text-align: left;\">Tick每秒嘀嗒的次数称为时间解析度，中断次数Hz</p><p style=\"text-align: left;\">100Hz：一秒嘀嗒100次，每秒100次时间中断</p><p style=\"text-align: left;\">1000Hz：一秒嘀嗒1000次，1ms嘀嗒一次</p><p style=\"text-align: left;\">通常每次滴答都会产生可抢的时钟中断</p><p style=\"text-align: left;\"><strong>调度器</strong>：其任务是在程序之间共享CPU时间, 创造并行执行的错觉, 该任务分为两个不同的部分, 其中一个涉及调度策略, 另外一个涉及上下文切换。内核必须提供一种方法, 在各个进程之间尽可能公平地共享CPU时间, 而同时又要考虑不同的任务优先级.</p><p style=\"text-align: left;\">调度器的一个重要目标是有效地分配 CPU 时间片，同时提供很好的用户体验。调度器还需要面对一些互相冲突的目标，例如既要为关键实时任务最小化响应时间, 又要最大限度地提高 CPU 的总体利用率.</p><p style=\"text-align: left;\">调度器的一般原理是, 按所需分配的计算能力, 向系统中每个进程提供最大的公正性, 或者从另外一个角度上说, 他试图确保没有进程被亏待.</p><p style=\"text-align: left;\"><strong>进程分类</strong>：</p><p style=\"text-align: left;\"> &nbsp; &nbsp;交互式进程（I/O）：例如编辑器，大量时间等待IO上与CPU打交道比较少</p><p style=\"text-align: left;\"> &nbsp; &nbsp;批处理进程（CPU）：守护进程，大量CPU时间</p><p style=\"text-align: left;\"> &nbsp; &nbsp;实时进程(Real-time)：立即响应，优先级最高</p><p style=\"text-align: left;\"><br></p><table style=\"width: auto;\"><tbody><tr><td colSpan=\"1\" rowSpan=\"1\" width=\"236\">类型</td><td colSpan=\"1\" rowSpan=\"1\" width=\"236\">描述</td><td colSpan=\"1\" rowSpan=\"1\" width=\"236\">示例</td></tr><tr><td colSpan=\"1\" rowSpan=\"1\" width=\"236\">交互式进程(interactive process)</td><td colSpan=\"1\" rowSpan=\"1\" width=\"236\">此类进程经常与用户进行交互, 因此需要花费很多时间等待键盘和鼠标操作. 当接受了用户的输入后, 进程必须很快被唤醒, 否则用户会感觉系统反应迟钝</td><td colSpan=\"1\" rowSpan=\"1\" width=\"236\">shell, 文本编辑程序和图形应用程序</td></tr><tr><td colSpan=\"1\" rowSpan=\"1\" width=\"236\">批处理进程(batch process)</td><td colSpan=\"1\" rowSpan=\"1\" width=\"236\">此类进程不必与用户交互, 因此经常在后台运行. 因为这样的进程不必很快相应, 因此常受到调度程序的怠慢</td><td colSpan=\"1\" rowSpan=\"1\" width=\"236\">程序语言的编译程序, 数据库搜索引擎以及科学计算</td></tr><tr><td colSpan=\"1\" rowSpan=\"1\" width=\"236\">实时进程(real-time process)</td><td colSpan=\"1\" rowSpan=\"1\" width=\"236\">这些进程由很强的调度需要, 这样的进程绝不会被低优先级的进程阻塞. 并且他们的响应时间要尽可能的短</td><td colSpan=\"1\" rowSpan=\"1\" width=\"236\">视频音频应用程序, 机器人控制程序以及从物理传感器上收集数据的程序</td></tr></tbody></table><p style=\"text-align: left;\">如何设定是批处理进程优先级高呢还是交互式进程高呢？如果批处理进程优先级高，对于交互式进程的应用，例如编辑器输入一个字母或者数字半天没有响应；如果交互式进程优先级高，对于CPU来说大部分时间是空闲的，所以很浪费资源。因此调度器引用了以下分配策略：</p><p style=\"text-align: left;\"> &nbsp; &nbsp;CPU密集型（批处理进程）:时间片长，优先级低</p><p style=\"text-align: left;\"> &nbsp; &nbsp;IO密集型（交互式进程）:时间片短，优先级高</p><p style=\"text-align: left;\"><strong>进程优先级（priority）定义</strong>：1、实时优先级；2、静态优先级。优先级范围从1~139</p><p style=\"text-align: left;\">实时优先级：用1~99表示，数字越小，优先级越低</p><p style=\"text-align: left;\">静态优先级：用100~139表示，数字越小，优先级越高</p><p style=\"text-align: left;\">实时优先级比静态优先级高，通常内核进程都是实时优先级。优先级为RT就是实时优先级（1~99），而20是从100之后的20（即120），原因它的nice值是为0，这是站在用户模式是讲。如下图：</p><p style=\"text-align: left;\"> <img src=\"http://120.46.13.13:8080/images/image_20240717143414.png\" alt=\"\" data-href=\"\" style=\"\"></p><p style=\"text-align: left;\"><strong>查看进程优先级</strong>：ps -e -o class,rtprio,nice,pri,nice,cmd用这个命令可以查看优先级， class：表示调度类别</p><p style=\"text-align: left;\">rtprio：实时优先级</p><p style=\"text-align: left;\">nice：调整静态优先级。nice值是-20到19，对应的是100到139，nice值为0对 &nbsp; 应的为120，默认为0</p><p style=\"text-align: left;\">pri：非实时优先级（静态优先级）</p><p style=\"text-align: left;\">cmd：执行的命令</p><p><br></p>', '', 5, 0, '2024-07-17 14:25:29.883', '2024-07-17 14:34:29.449');
INSERT INTO `articles` (`id`, `user_id`, `category_id`, `title`, `content`, `head_image`, `read_cnt`, `status`, `created_at`, `updated_at`) VALUES (20, 4, 2, 'Switch Statements', '<p style=\"text-align: start;\">In this part of our compiler writing journey, we are going to implement the \'switch\' statement. This is really tricky for several reasons which I\'ll cover. So let\'s start with an example and look at the implications.</p><p style=\"text-align: start;\"><br></p><h2>An Example Switch Statement</h2><p><br></p><pre><code >  switch(x) {\n    case 1:  printf(\"One\\n\");  break;\n    case 2:  printf(\"Two\\n\");  break;\n    case 3:  printf(\"Three\\n\");\n    default: printf(\"More than two\\n\");\n  }\n  \n  </code></pre><p style=\"text-align: start;\">This is like a multi-way \'if\' statement where the value of <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>x</code></span> chooses the branch to take. However, we need to insert the <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>break</code></span> statement to bypass all the other branches; if we leave out the <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>break</code></span> statement, the branch that we are in falls through and continues on with the execution of the next branch.</p><p style=\"text-align: start;\">The expression for the \'switch\' decision has to be integer, and all of the case options have to be integer literals. We can\'t say <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>case 3*y+17</code></span>, for example.</p><p style=\"text-align: start;\">The <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>default</code></span> case catches all values that are not given by previous cases. It has to appear as the last case in the list. Also, we cannot have duplicate case values, so <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>case 2: ...; case 2</code></span> is not permitted.</p><p style=\"text-align: start;\"><br></p><h2>Converting the Above into Assembly</h2><p style=\"text-align: start;\">One way to translate a \'switch\' statement into assembly is to treat it as a multi-way \'if\' statement. This would mean that we would compare <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>x</code></span> against integer values, one after the other, and go into or skip over sections of assembly code as required. This would work but it makes the assembly code inefficient, especially if you consider this example:</p><p style=\"text-align: start;\"><br></p><pre><code >  switch (2 * x - (18 +y)/z) { ... }\n  \n  </code></pre><p style=\"text-align: start;\">Given our current \"<a href=\"https://en.wikipedia.org/wiki/KISS_principle\" target=\"\">KISS</a>\" compiler\'s operation, we would have to evaluate the expression again and again for each comparison against a literal value.</p><p style=\"text-align: start;\">It makes more sense to evaluate the \'switch\' expression once. Then, compare this value against a table of case literal values. When we find a match, we jump to the code branch associated with the case values. This is known as a <a href=\"https://en.wikipedia.org/wiki/Branch_table\" target=\"\">jump table</a>.</p><p style=\"text-align: start;\">It means that, for each case option, we will need to create a label to place at the beginning of the code for this option. As an example, the jump table for the first example above might look like:</p><p style=\"text-align: start;\"><br></p><table style=\"width: auto;\"><tbody><tr><th colSpan=\"1\" rowSpan=\"1\" width=\"auto\">Case Value</th><th colSpan=\"1\" rowSpan=\"1\" width=\"auto\">Label</th></tr><tr><td colSpan=\"1\" rowSpan=\"1\" width=\"auto\">1</td><td colSpan=\"1\" rowSpan=\"1\" width=\"auto\">L18</td></tr><tr><td colSpan=\"1\" rowSpan=\"1\" width=\"auto\">2</td><td colSpan=\"1\" rowSpan=\"1\" width=\"auto\">L19</td></tr><tr><td colSpan=\"1\" rowSpan=\"1\" width=\"auto\">3</td><td colSpan=\"1\" rowSpan=\"1\" width=\"auto\">L22</td></tr><tr><td colSpan=\"1\" rowSpan=\"1\" width=\"auto\">default</td><td colSpan=\"1\" rowSpan=\"1\" width=\"auto\">L26</td></tr></tbody></table><p style=\"text-align: start;\">We also need a label to mark the code after the \'switch\' statement. When one code branch wants to <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>break;</code></span>, we jump to this \'switch\' end label. Otherwise, we let the code branch fall through into the next code branch.</p><p style=\"text-align: start;\"><br></p><h2>Parsing Implications</h2><p style=\"text-align: start;\">All of the above is fine and good, except that we have to parse a \'switch\' statement from top to bottom. This means that we won\'t know how big the jump table should be until after we have parsed all of the cases. This also means that, unless we perform some clever tricks, we will have generated the assembly code for all the cases <em>before</em> we can generate the jump table.</p><p style=\"text-align: start;\">As you know, I\'m writing this compiler following the \"KISS principle\": keep it simple, stupid! So I am avoiding the clever tricks, but this means that, yes, we are going to delay the output of the jump table until after we generate all of the assembly code for the various cases.</p><p style=\"text-align: start;\">Visually, here is how we are going to lay out our code:</p><p style=\"text-align: start;\">The code to evaluate the switch decision is at the top, as we parse it first. We don\'t want to continue on into the first case, so we can jump to a label which we will output later.</p><p style=\"text-align: start;\">Then we parse each case statement and generate the corresponding assembly code. We will have already generated an \"end of switch\" label, so we can jump to it. Again, we will output this label later.</p><p style=\"text-align: start;\">As we generate each case, we get a label for it and output this label. Once all the cases and the default case (if any) are output, we can now generate the jump table.</p><p style=\"text-align: start;\">But now we need some code to walk the jump table, compare the switch decision against each case value, and jump appropriately. We could generate this assembly code for each and every \'switch\' statement but, if this jump handling code is large, we will be wasting memory. It\'s better to have one copy of the jump handling code in memory, but now we have to jump to it! Even worse, this code doesn\'t know which register holds the switch decision result, so we will have to copy this register into a known register, and copy the base of the jump table into a known register.</p><p style=\"text-align: start;\">What we have done here is trade off complexity in the parsing and code generation for a spaghetti of assembly code with jumps all over the place. Well, the CPU can deal with the jump spaghetti, so for now it\'s a fair tradeoff. Obviously, a production compiler would do things differently.</p><p style=\"text-align: start;\">The red lines in the diagram show the flow of execution from the switch decision to loading the registers to the jump table handling and finally to the specific case code. The green line shows that the base address of the jump table is passed to the jump table handling code. Finally, the blue lines shows that the case ended with a <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>break;</code></span> which jumped to the end of the switch assembly code.</p><p style=\"text-align: start;\">So, the assembly output is ugly but it does work. Now that we\'ve seen how we are going to implement \'switch\' statements, let\'s actually do it.</p><p style=\"text-align: start;\"><br></p><h2>New Keywords and Tokens</h2><p style=\"text-align: start;\">We have two new tokens, T_CASE and T_DEFAULT, to go along with the new <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>case</code></span> and <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>default</code></span> keywords. As always, browse the code to see how this is done.</p><p style=\"text-align: start;\"><br></p><h2>New AST Node Types</h2><p style=\"text-align: start;\">We need to build the AST tree to represent \'switch\' statements. The structure of a \'switch\' statement is in no way a binary tree like our expressions. But it is <em>our</em> AST tree, so we can shape it any way that suits us. So I sat down for a bit and decided to go with this structure:</p><p style=\"text-align: start;\">The root of the \'switch\' tree is A_SWITCH, On the left is the sub-tree with the expression that calculates the switch\'s condition. On the right we have a linked list of A_CASE nodes, one for each case. Finally, there is an optional A_DEFAULT to capture any default case.</p><p style=\"text-align: start;\">The <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>intvalue</code></span> field in each A_CASE node will hold the case value which the expression must match. The left child sub-tree will hold the details of the compound statement which is the case\'s body. At this point, we don\'t have any jump labels or the jump table: we will generate this later.</p><p style=\"text-align: start;\"><br></p><h2>Parsing the Switch Statement</h2><p style=\"text-align: start;\">With all the above on-board, we\'re now ready to look at the parsing of a \'switch\' statement. There is quite a lot of error checking code here, so I will take it in small sections. This code is in <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>stmt.c</code></span> and is called from <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>single_statement()</code></span>:</p><p style=\"text-align: start;\"><br></p><pre><code >    case T_SWITCH:\n      return (switch_statement());\n      \n      </code></pre><p style=\"text-align: start;\">Let\'s go..</p><p style=\"text-align: start;\"><br></p><pre><code >// Parse a switch statement and return its AST\nstatic struct ASTnode *switch_statement(void) {\n  struct ASTnode *left, *n, *c, *casetree= NULL, *casetail;\n  int inloop=1, casecount=0;\n  int seendefault=0;\n  int ASTop, casevalue;\n\n  // Skip the \'switch\' and \'(\'\n  scan(&Token);\n  lparen();\n\n  // Get the switch expression, the \')\' and the \'{\'\n  left= binexpr(0);\n  rparen();\n  lbrace();\n\n  // Ensure that this is of int type\n  if (!inttype(left-&gt;type))\n    fatal(\"Switch expression is not of integer type\");\n    \n    </code></pre><p style=\"text-align: start;\">OK, so there\'s a lot of local variables at the top which should clue you in that we will have to deal with some state in this function. This first section is easy, though: parse the <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>switch (expression) {</code></span> syntax, get the AST for the expression and ensure that its is of integer type.</p><p style=\"text-align: start;\"><br></p><pre><code >  // Build an A_SWITCH subtree with the expression as\n  // the child\n  n= mkastunary(A_SWITCH, 0, left, NULL, 0);\n\n  // Now parse the cases\n  Switchlevel++;\n  \n  </code></pre><p style=\"text-align: start;\">We\'ve got the switch decision tree, so we can now build the A_SWITCH node which we will return. Do you remember that we could only let a <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>break;</code></span> occur when we are inside at least one loop. Well, now we also have to let <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>break;</code></span> happen when there is at least one \'switch\' statement. Thus, there is a new global variable, <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>Switchlevel</code></span> to record this.</p><p style=\"text-align: start;\"><br></p><pre><code >  // Now parse the cases\n  Switchlevel++;\n  while (inloop) {\n    switch(Token.token) {\n      // Leave the loop when we hit a \'}\'\n      case T_RBRACE: if (casecount==0)\n                        fatal(\"No cases in switch\");\n                     inloop=0; break;\n  ...\n  }\n  \n  </code></pre><p style=\"text-align: start;\">The loop is controlled by <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>inloop</code></span> which starts at one. When we hit a \'}\' token, we reset it to zero and break out of this \'switch\' statement, thus ending the loop. We also check that we have seen at least one case.</p><blockquote style=\"text-align: start;\">It\'s a bit weird using a \'switch\' statement to parse \'switch\' statements.</blockquote><p style=\"text-align: start;\">Now we move on to the parsing of <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>case</code></span> and <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>default</code></span>:</p><p style=\"text-align: start;\"><br></p><pre><code >      case T_CASE:\n      case T_DEFAULT:\n        // Ensure this isn\'t after a previous \'default\'\n        if (seendefault)\n          fatal(\"case or default after existing default\");\n          \n          </code></pre><p style=\"text-align: start;\">We have a lot of common code to perform, so both tokens fall into the same code. First, ensure that we haven\'t already seen a default case, and this has to be the last case in the series.</p><p style=\"text-align: start;\"><br></p><pre><code >        // Set the AST operation. Scan the case value if required\n        if (Token.token==T_DEFAULT) {\n          ASTop= A_DEFAULT; seendefault= 1; scan(&Token);\n        } else ...\n        \n        </code></pre><p style=\"text-align: start;\">If we are parsing <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>default:</code></span>, then there is no following integer value. Skip over the keyword and record that we have seen a default case.</p><p style=\"text-align: start;\"><br></p><pre><code >        } else  {\n          ASTop= A_CASE; scan(&Token);\n          left= binexpr(0);\n          // Ensure the case value is an integer literal\n          if (left-&gt;op != A_INTLIT)\n            fatal(\"Expecting integer literal for case value\");\n          casevalue= left-&gt;intvalue;\n\n          // Walk the list of existing case values to ensure\n          // that there isn\'t a duplicate case value\n          for (c= casetree; c != NULL; c= c -&gt; right)\n            if (casevalue == c-&gt;intvalue)\n              fatal(\"Duplicate case value\");\n        }\n        \n        </code></pre><p style=\"text-align: start;\">This code deals specifically with <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>case &lt;value&gt;:</code></span>. We read in the value after the case using <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>binexpr()</code></span>. Now, I could have been \"clever\" and called <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>primary()</code></span> instead which goes straight to parsing integer literals. However, <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>primary()</code></span> can call <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>binexpr()</code></span> anyway, so it really doesn\'t make any difference: we are still going to have to error check the resulting tree to ensure that it is an A_INTLIT node only.</p><p style=\"text-align: start;\">Then we walk the list of previous A_CASE nodes that we have (<span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>casetree</code></span> points to the head of this list) to ensure that we don\'t have any duplicate case values.</p><p style=\"text-align: start;\">Along the way, we have set the <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>ASTop</code></span> variable to either A_CASE for a case with an integer literal value or A_DEFAULT for the default case. We can now perform the code common to both.</p><p style=\"text-align: start;\"><br></p><pre><code >        // Scan the \':\' and get the compound expression\n        match(T_COLON, \":\");\n        left= compound_statement(); casecount++;\n\n        // Build a sub-tree with the compound statement as the left child\n        // and link it in to the growing A_CASE tree\n        if (casetree==NULL) {\n          casetree= casetail= mkastunary(ASTop, 0, left, NULL, casevalue);\n        } else {\n          casetail-&gt;right= mkastunary(ASTop, 0, left, NULL, casevalue);\n          casetail= casetail-&gt;right;\n        }\n        break;\n        \n        </code></pre><p style=\"text-align: start;\">Check that the next token is a \':\'. Get the AST sub-tree with the compound statement in it. Build an A_CASE or A_DEFAULT node with this sub-tree as the left child, and link this to the linked list of A_CASE/A_DEFAULT nodes: <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>casetree</code></span> is the head and <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>casetail</code></span> is the tail of this list.</p><p style=\"text-align: start;\"><br></p><pre><code >      default:\n        fatald(\"Unexpected token in switch\", Token.token);\n    }\n  }\n  \n  </code></pre><p style=\"text-align: start;\">There should only be <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>case</code></span> and <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>default</code></span> keywords in the \'switch\' body, so ensure that this is the case.</p><p style=\"text-align: start;\"><br></p><pre><code >  Switchlevel--;\n\n  // We have a sub-tree with the cases and any default. Put the\n  // case count into the A_SWITCH node and attach the case tree.\n  n-&gt;intvalue= casecount;\n  n-&gt;right= casetree;\n  rbrace();\n\n  return(n);\n  \n  </code></pre><p style=\"text-align: start;\">We\'ve finally parsed all of the cases and the default case, and we now have the count of them and the list which <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>casetree</code></span> points to. Add these values to the A_SWITCH node and return this as the final tree.</p><p style=\"text-align: start;\">OK, so that was a substantial amount of parsing. Now we need to turn our attention to code generation.</p><p style=\"text-align: start;\"><br></p><h2>Switch Code Generation: An Example.</h2><p style=\"text-align: start;\">At this point I think it would be worth seeing the assembly output of an example \'switch\' statement so that you can see how the code matches the graphic of execution flow that I gave at the top. Here is the example:</p><p style=\"text-align: start;\"><br></p><pre><code >#include &lt;stdio.h&gt;\n\nint x; int y;\n\nint main() {\n  switch(x) {\n    case 1:  { y= 5; break; }\n    case 2:  { y= 7; break; }\n    case 3:  { y= 9; }\n    default: { y= 100; }\n  }\n  return(0);\n}\n\n</code></pre><p style=\"text-align: start;\">First up, yes we do need \'{\' ... \'}\' around the case bodies. This is because I still haven\'t solved the \"dangling else\" problem, so all compound statements have to be surrounded by \'{\' ... \'}\'.</p><p style=\"text-align: start;\">I\'m going to leave out the jump table handling code for now, but here is the assembly output for this example:</p><p style=\"text-align: start;\">The code that loads <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>x</code></span> into a register is at the top, and it jumps down past the jump table. As the jump table handling code doesn\'t know which register this will be, we always load the value into <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>%rax</code></span>, and we load the jump table\'s base address into <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>%rdx</code></span>.</p><p style=\"text-align: start;\">The jump table itself has this structure:</p><ul><li style=\"text-align: start;\">First is the number of cases with integer values</li><li style=\"text-align: start;\">Next is a set of value/label pairs, one for each case</li><li style=\"text-align: start;\">Finally there is the label of the default case. If there is no default case, this has to be the label of the \'switch\' end, so that we do no code if there is no matching case.</li></ul><p style=\"text-align: start;\">The jump table handling code (which we will look at soon) interprets the jump table and jumps to one of the labels in this table. Let\'s assume that we have jumped to <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>L11</code></span> which is <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>case 2:</code></span>. We perform the code for this case option. This option has a <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>break;</code></span> statement, so there is a jump to <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>L9</code></span> which is the label for the end of the \'switch\' statement.</p><p style=\"text-align: start;\"><br></p><h2>The Jump Table Handling Code</h2><p style=\"text-align: start;\">You already know that x86-64 assembly code isn\'t my forte. Therefore, I\'ve borrowed the jump table handling code directly from <a href=\"http://www.t3x.org/subc/\" target=\"\">SubC</a>. I\'ve added it to the <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>cgpreamble()</code></span> function in <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>cg.c</code></span>, so that it is output for every assembly file that we create. Here is the commented code:</p><p style=\"text-align: start;\"><br></p><pre><code ># internal switch(expr) routine\n# %rsi = switch table, %rax = expr\n\nswitch:\n        pushq   %rsi            # Save %rsi\n        movq    %rdx,%rsi       # Base of jump table -&gt; %rsi\n        movq    %rax,%rbx       # Switch value -&gt; %rbx\n        cld                     # Clear direction flag\n        lodsq                   # Load count of cases into %rcx,\n        movq    %rax,%rcx       # incrementing %rsi in the process\nnext:\n        lodsq                   # Get the case value into %rdx\n        movq    %rax,%rdx\n        lodsq                   # and the label address into %rax\n        cmpq    %rdx,%rbx       # Does switch value matches the case?\n        jnz     no              # No, jump over this code\n        popq    %rsi            # Restore %rsi\n        jmp     *%rax           # and jump to the chosen case\nno:\n        loop    next            # Loop for the number of cases\n        lodsq                   # Out of loop, load default label address\n        popq    %rsi            # Restore %rsi\n        jmp     *%rax           # and jump to the default case\n\n\n</code></pre><p style=\"text-align: start;\">We need to thanks Nils Holm for writing this, as I would never have arrived at this code!</p><p style=\"text-align: start;\">Now we can look at how the above assembly code gets generated. Fortunately, we already have lots of useful functions in <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>cg.c</code></span> which we can reuse.</p><p style=\"text-align: start;\"><br></p><h2>Generating the Assembly Code</h2><p style=\"text-align: start;\">In <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>genAST()</code></span> in <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>gen.c</code></span>, up near the top we identify an A_SWITCH node and call a function to deal with this node and the tree below it.</p><p style=\"text-align: start;\"><br></p><pre><code >    case A_SWITCH:\n      return (genSWITCH(n));\n      \n      </code></pre><p style=\"text-align: start;\">So let\'s look at this new function in stages:</p><p style=\"text-align: start;\"><br></p><pre><code >// Generate the code for a SWITCH statement\nstatic int genSWITCH(struct ASTnode *n) {\n  int *caseval, *caselabel;\n  int Ljumptop, Lend;\n  int i, reg, defaultlabel = 0, casecount = 0;\n  struct ASTnode *c;\n\n  // Create arrays for the case values and associated labels.\n  // Ensure that we have at least one position in each array.\n  caseval = (int *) malloc((n-&gt;intvalue + 1) * sizeof(int));\n  caselabel = (int *) malloc((n-&gt;intvalue + 1) * sizeof(int));\n  \n  </code></pre><p style=\"text-align: start;\">The reason for the <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>+1</code></span> here is that we may have a default case which needs a label even though it doesn\'t have a case value.</p><p style=\"text-align: start;\"><br></p><pre><code >  // Generate labels for the top of the jump table, and the\n  // end of the switch statement. Set a default label for\n  // the end of the switch, in case we don\'t have a default.\n  Ljumptop = genlabel();\n  Lend = genlabel();\n  defaultlabel = Lend;\n  \n  </code></pre><p style=\"text-align: start;\">These labels are made but not output as assembly yet. Until we have a default label, we set it to <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>Lend</code></span>.</p><p style=\"text-align: start;\"><br></p><pre><code >  // Output the code to calculate the switch condition\n  reg = genAST(n-&gt;left, NOLABEL, NOLABEL, NOLABEL, 0);\n  cgjump(Ljumptop);\n  genfreeregs();\n  \n  </code></pre><p style=\"text-align: start;\">We output the code to jump to the code after the jump table even though it hasn\'t been output. We can also free all the registers at this point.</p><p style=\"text-align: start;\"><br></p><pre><code >  // Walk the right-child linked list to\n  // generate the code for each case\n  for (i = 0, c = n-&gt;right; c != NULL; i++, c = c-&gt;right) {\n\n    // Get a label for this case. Store it\n    // and the case value in the arrays.\n    // Record if it is the default case.\n    caselabel[i] = genlabel();\n    caseval[i] = c-&gt;intvalue;\n    cglabel(caselabel[i]);\n    if (c-&gt;op == A_DEFAULT)\n      defaultlabel = caselabel[i];\n    else\n      casecount++;\n\n    // Generate the case code. Pass in the end label for the breaks\n    genAST(c-&gt;left, NOLABEL, NOLABEL, Lend, 0);\n    genfreeregs();\n  }\n  \n  </code></pre><p style=\"text-align: start;\">This is the code that both generates the label for each case and also outputs the assembly code which is the body of the case. We store the case value and the case label in the two arrays. And, if this is the default case, we can update <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>defaultlabel</code></span> with the correct label.</p><p style=\"text-align: start;\">Also note that <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>genAST()</code></span> gets passed <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>Lend</code></span> which is the label after our \'switch\' code. This allows any <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>break;</code></span> in the case body to jump out to what comes next.</p><p style=\"text-align: start;\"><br></p><pre><code >  // Ensure the last case jumps past the switch table\n  cgjump(Lend);\n\n  // Now output the switch table and the end label.\n  cgswitch(reg, casecount, Ljumptop, caselabel, caseval, defaultlabel);\n  cglabel(Lend);\n  return (NOREG);\n}\n\n</code></pre><p style=\"text-align: start;\">We can\'t rely on the programmer to end their last case with a <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>break;\'</code></span> statement, so we force the last case to have a jump to the end of the switch statement.</p><p style=\"text-align: start;\">At this point we have:</p><ul><li style=\"text-align: start;\">the register which has the switch value</li><li style=\"text-align: start;\">the array of case values</li><li style=\"text-align: start;\">the array of case labels</li><li style=\"text-align: start;\">the number of cases</li><li style=\"text-align: start;\">some useful labels</li></ul><p style=\"text-align: start;\">We pass all of these into <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>cgswitch()</code></span> in <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>cg.c</code></span>, and (apart from the code from SubC) this is the only new assembly code we need to introduce for this part.</p><p style=\"text-align: start;\"><br></p><h2><span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>cgswitch()</code></span></h2><p style=\"text-align: start;\">Here, we need to build the jump table and load the registers so that we can jump to the <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>switch</code></span> assembly code. As a reminder, here is the jump table structure:</p><ul><li style=\"text-align: start;\">First is the number of cases with integer values</li><li style=\"text-align: start;\">Next is a set of value/label pairs, one for each case</li><li style=\"text-align: start;\">Finally there is the label of the default case. If there is no default case, this has to be the label of the \'switch\' end, so that we do no code if there is no matching case.</li></ul><p style=\"text-align: start;\">For our example, the jump table looks like:</p><p style=\"text-align: start;\"><br></p><pre><code >L14:                                    # Switch jump table\n        .quad   3                       # Three case values\n        .quad   1, L10                  # case 1: jump to L10\n        .quad   2, L11                  # case 2: jump to L11\n        .quad   3, L12                  # case 3: jump to L12\n        .quad   L13                     # default: jump to L13\n\n\n</code></pre><p style=\"text-align: start;\">Here is how we generate all of this.</p><p style=\"text-align: start;\"><br></p><pre><code >// Generate a switch jump table and the code to\n// load the registers and call the switch() code\nvoid cgswitch(int reg, int casecount, int toplabel,\n              int *caselabel, int *caseval, int defaultlabel) {\n  int i, label;\n\n  // Get a label for the switch table\n  label = genlabel();\n  cglabel(label);\n  \n  </code></pre><p style=\"text-align: start;\">This is the <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>L14:</code></span> above.</p><p style=\"text-align: start;\"><br></p><pre><code >  // Heuristic. If we have no cases, create one case\n  // which points to the default case\n  if (casecount == 0) {\n    caseval[0] = 0;\n    caselabel[0] = defaultlabel;\n    casecount = 1;\n  }\n  \n  </code></pre><p style=\"text-align: start;\">We must have at least one case value/label pair in the jump table. This code makes one that points at the default case. The case value is irrelevant: if it matches, fine. If not, we jump to the default case anyway.</p><p style=\"text-align: start;\"><br></p><pre><code >  // Generate the switch jump table.\n  fprintf(Outfile, \"\\t.quad\\t%d\\n\", casecount);\n  for (i = 0; i &lt; casecount; i++)\n    fprintf(Outfile, \"\\t.quad\\t%d, L%d\\n\", caseval[i], caselabel[i]);\n  fprintf(Outfile, \"\\t.quad\\tL%d\\n\", defaultlabel);\n  \n  </code></pre><p style=\"text-align: start;\">Here is the code to generate the jump table. Nice and easy.</p><p style=\"text-align: start;\"><br></p><pre><code >  // Load the specific registers\n  cglabel(toplabel);\n  fprintf(Outfile, \"\\tmovq\\t%s, %%rax\\n\", reglist[reg]);\n  fprintf(Outfile, \"\\tleaq\\tL%d(%%rip), %%rdx\\n\", label);\n  fprintf(Outfile, \"\\tjmp\\tswitch\\n\");\n}\n\n</code></pre><p style=\"text-align: start;\">Finally, load the <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>%rax</code></span> register with the switch value, load <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>%rdx</code></span> with the label of the jump table and call the <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>switch</code></span> code.</p><p style=\"text-align: start;\"><br></p><h2>Testing The Code</h2><p style=\"text-align: start;\">I\'ve augmented our example with a loop so that all cases in the \'switch\' statement get tested This is the file <span style=\"background-color: var(--bgColor-neutral-muted, var(--color-neutral-muted));\"><code>tests/input74.c</code></span>:</p><p style=\"text-align: start;\"><br></p><pre><code >#include &lt;stdio.h&gt;\n\nint main() {\n  int x;\n  int y;\n  y= 0;\n\n  for (x=0; x &lt; 5; x++) {\n    switch(x) {\n      case 1:  { y= 5; break; }\n      case 2:  { y= 7; break; }\n      case 3:  { y= 9; }\n      default: { y= 100; }\n    }\n    printf(\"%d\\n\", y);\n  }\n  return(0);\n}\n\n</code></pre><p style=\"text-align: start;\">And here is the output from the program:</p><p style=\"text-align: start;\"><br></p><pre><code >100\n5\n7\n100\n100\n\n\n</code></pre><p style=\"text-align: start;\">Note that the value 9 is not output, because we fall into the default case when we are doing case 3.</p><p style=\"text-align: start;\"><br></p><h2>Conclusion and What\'s Next</h2><p style=\"text-align: start;\">We\'ve just implemented our first really big new statement in our compiler, the \'switch\' statement. As I\'ve never done this before, I essentially followed the SubC implementation. There are many other, more efficient, ways to implement \'switch\', but I applied the \"KISS principle\" here. That said, it still was quite a complicated implementation.</p><p style=\"text-align: start;\">If you are still reading at this point, congratulations on your staying power!</p><p style=\"text-align: start;\">I\'m starting to get annoyed with the compulsory \'{\' ... \'}\' around all of our compound statements. So, in the next part of our compiler writing journey, I will bite the bullet and attempt to solve the \"dangling else\" problem. <a href=\"https://github.com/DoctorWkt/acwj/blob/master/38_Dangling_Else/Readme.md\" target=\"\">Next step</a></p><p style=\"text-align: start;\"><br></p><p style=\"text-align: start;\"><br></p><p style=\"text-align: start;\"><br></p><p><br></p>', '', 3, 0, '2024-07-17 14:37:32.297', '2024-07-17 15:05:13.603');
COMMIT;

-- ----------------------------
-- Table structure for categories
-- ----------------------------
DROP TABLE IF EXISTS `categories`;
CREATE TABLE `categories` (
  `id` bigint NOT NULL AUTO_INCREMENT,
  `category_name` varchar(50) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=5 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;

-- ----------------------------
-- Records of categories
-- ----------------------------
BEGIN;
INSERT INTO `categories` (`id`, `category_name`) VALUES (1, 'Database');
INSERT INTO `categories` (`id`, `category_name`) VALUES (2, 'Compilers');
INSERT INTO `categories` (`id`, `category_name`) VALUES (3, 'Computer-Networking');
INSERT INTO `categories` (`id`, `category_name`) VALUES (4, 'Operating-System-Concepts');
COMMIT;

-- ----------------------------
-- Table structure for collects
-- ----------------------------
DROP TABLE IF EXISTS `collects`;
CREATE TABLE `collects` (
  `user_id` bigint unsigned NOT NULL,
  `article_id` bigint unsigned NOT NULL,
  PRIMARY KEY (`user_id`,`article_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;

-- ----------------------------
-- Records of collects
-- ----------------------------
BEGIN;
COMMIT;

-- ----------------------------
-- Table structure for comments
-- ----------------------------
DROP TABLE IF EXISTS `comments`;
CREATE TABLE `comments` (
  `id` bigint unsigned NOT NULL AUTO_INCREMENT,
  `created_at` datetime(3) DEFAULT NULL,
  `updated_at` datetime(3) DEFAULT NULL,
  `deleted_at` datetime(3) DEFAULT NULL,
  `content` text NOT NULL,
  `user_id` bigint unsigned NOT NULL,
  `article_id` bigint unsigned NOT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_comments_deleted_at` (`deleted_at`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;

-- ----------------------------
-- Records of comments
-- ----------------------------
BEGIN;
COMMIT;

-- ----------------------------
-- Table structure for follows
-- ----------------------------
DROP TABLE IF EXISTS `follows`;
CREATE TABLE `follows` (
  `follower_id` bigint unsigned NOT NULL,
  `followee_id` bigint unsigned NOT NULL,
  PRIMARY KEY (`follower_id`,`followee_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;

-- ----------------------------
-- Records of follows
-- ----------------------------
BEGIN;
COMMIT;

-- ----------------------------
-- Table structure for users
-- ----------------------------
DROP TABLE IF EXISTS `users`;
CREATE TABLE `users` (
  `id` bigint unsigned NOT NULL AUTO_INCREMENT,
  `created_at` datetime(3) DEFAULT NULL,
  `updated_at` datetime(3) DEFAULT NULL,
  `deleted_at` datetime(3) DEFAULT NULL,
  `user_name` longtext NOT NULL,
  `phone_number` varchar(191) NOT NULL,
  `password` varchar(255) NOT NULL,
  `avatar` varchar(255) NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `uni_users_phone_number` (`phone_number`),
  KEY `idx_users_deleted_at` (`deleted_at`)
) ENGINE=InnoDB AUTO_INCREMENT=6 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;

-- ----------------------------
-- Records of users
-- ----------------------------
BEGIN;
INSERT INTO `users` (`id`, `created_at`, `updated_at`, `deleted_at`, `user_name`, `phone_number`, `password`, `avatar`) VALUES (1, '2024-07-16 23:00:02.155', '2024-07-16 23:00:02.155', NULL, 'nightgoodl', '15369514356', '$2a$10$uVtFZ88oJNT0Gz7EIgZ4EOfBvGE3.KF4bz6uShgh6qciSKjCyxa2G', '/images/default_avatar1.png');
INSERT INTO `users` (`id`, `created_at`, `updated_at`, `deleted_at`, `user_name`, `phone_number`, `password`, `avatar`) VALUES (2, '2024-07-17 09:12:52.777', '2024-07-17 09:12:52.777', NULL, 'ttang', '18964698880', '$2a$10$wkFyP457MfBBc42IJCg8ueSGVkvWFQ6yBC5Ju23b4L63bdWbQa65m', '/images/default_avatar1.png');
INSERT INTO `users` (`id`, `created_at`, `updated_at`, `deleted_at`, `user_name`, `phone_number`, `password`, `avatar`) VALUES (3, '2024-07-17 09:13:04.329', '2024-07-17 09:13:04.329', NULL, '555', '15938328620', '$2a$10$EOLiwM8p0gRoiyt2R9m.Y.AGZ9I7F3n/dIenAHDwH/j.gdH2L/X3G', '/images/default_avatar1.png');
INSERT INTO `users` (`id`, `created_at`, `updated_at`, `deleted_at`, `user_name`, `phone_number`, `password`, `avatar`) VALUES (4, '2024-07-17 09:15:26.454', '2024-07-17 14:04:12.053', NULL, 'blog_admin1', '12345678901', '$2a$10$ieWdKp.YcRVIhtSmjkfp7.Qmlt1TW/f4Gp.Qt2SiWxqqqzKva8vmK', '/images/default_avatar1.png');
INSERT INTO `users` (`id`, `created_at`, `updated_at`, `deleted_at`, `user_name`, `phone_number`, `password`, `avatar`) VALUES (5, '2024-07-17 14:03:36.008', '2024-07-17 14:04:25.675', NULL, 'admin_blog2', '12345678900', '$2a$10$afmvgG/zLQMP/tmLw.htYOvxCYdGkMen919yvf7gEW1etRyzi72Kq', '/images/default_avatar1.png');
COMMIT;

SET FOREIGN_KEY_CHECKS = 1;
